Build Monuments

Assign each node of a tree one of k types, so that cities that are directly connected or share a neighbor do not have the same type. This site adds the input protocol and constraints.

输入格式

The first line contains k n (1≤k≤10^9, 1≤n≤10^5); each of the next n−1 lines is an undirected edge u v, with cities numbered 1..n. The input is guaranteed to form a tree.

输出格式

Output the number of assignments in which any two cities at distance at most 2 have different types, modulo 1,000,000,007. This site adds this standard input protocol and the constraints.

样例 1

输入：

3 3
1 2
2 3

输出：

6

样例 2

输入：

2 1

输出：

2

样例 3

输入：

4 4
1 2
1 3
1 4

输出：

24