Consider the following boring game about removing nodes from a forest. Initially, the forest contains only one tree with N nodes, and your initial score is 0. The game then goes as follows:
Please calculate the expected value of your final score multiplied by N!, modulo 109 + 7.
The first line of input contains one integer N indicating the number of nodes in the initial tree.
Each of the following N - 1 lines contains two integers x and y, indicating that x-th node and y-th node are connected by an edge in the given tree. The nodes are numbered from 1 to N.
Output one number: the expected value of the final score of this boring game multiplied by N!, modulo 109 + 7.
2
1 2
6
3
1 2
2 3
34
Name |
---|