时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Bob has a tree with 
nodes, the set of the edges of this tree is 
.
Let
denote the edge set of n-clique, formally %7C1%5Cleq%20i%3Cj%5Cleq%20n%5C%7D)
Now give you an integer
, you need to find the number of pair )
satisfies the following conditions:
1.
, 
.
2.
, 
.
3.
is an edge set of a tree with nodes.
The answer may be very large, you only need to output the answer module
.
Let
Now give you an integer
1.
2.
3.
The answer may be very large, you only need to output the answer module
输入描述:
The first line has two integers.
Then there arelines, each line has two integers
denote an edge
in
输出描述:
Output the answer.