CODESPTE - Bytelandian Tours

The country of Byteland contains of N cities and N - 1 bidirectional roads between them such that there a path between any two cities. The cities are numbered 0 ... N - 1. The people were very unhappy about the time it took to commute, especially salesmen who had to go about every city selling goods. So it was decided that new roads would be built. A new road was built between every two cities which could be reached from each other by travelling on exactly two old roads.

Now a salesman situated in city 0, just like any other typical salesman, has to visit all cities exactly once and return back to city 0 in the end. In how many ways can he do this?

Input

The first line contains the number of test cases T. T test cases follow. The first line contains N, the number of cities in Byteland. The following N - 1 lines contain the description of the roads. The ith line contains two integers ai and bi, meaning that there was originally a road connecting cities with numbers ai and bi.

Output

Output T lines, one corresponding to each test case containing the required answer for that test case. Since the answers can be huge, output them modulo 1000000007.

Constraints

1 ≤ T ≤ 20

1 ≤ N ≤ 10000

0 ≤ ai, bi < N

Sample

Input:
2
3
0 1
1 2
5
0 1
1 2
2 3
2 4

Output:
2
4

Explanation

For the first case, a new road was build between cities 0 and 2. Now, the salesman has two tour possibilities: 0-1-2-0 or 0-2-1-0.


Added by:Varun Jalan
Date:2011-10-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint - InterviewStreet Contest

hide comments
2017-07-11 11:46:06
I got AC for the exact same problem at HackerRank: https://www.hackerrank.com/challenges/bytelandian-tours However, when I submitted the same solution here, I got WA. Problem author, could you please check your test data?
2012-03-14 03:31:51 apia
I submited the standard program.But it got WA too.Is there anything wrong with the data?

Last edit: 2012-03-14 03:41:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.