Problem Description
There are n people numbered from 1 to n. Each people have a unique message. Some pairs of people can send messages directly to each other, and this relationship forms a structure of a tree. In one turn, exactly one person sends all messages s/he currently has to another person. What is the minimum number of turns needed so that everyone has all the messages?
This is not your task. Your task is: count the number of ways that minimizes the number of turns. Two ways are different if there exists some k such that in the k-th turn, the sender or receiver is different in the two ways.
Input
First line, number of test cases, T.
Following are T test cases.
For each test case, the first line is number of people, n. Following are n-1 lines. Each line contains two numbers.
Sum of all n <= 1000000.
Output
T lines, each line is answer to the corresponding test case. Since the answers may be very large, you should output them modulo 109+7.
Sample Input
2
2
1 2
3
1 2
2 3
Sample Output
2
6