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.
输入解释
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.
输出解释
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.