F. Permutation via Tree
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a rooted tree containing $$$n$$$ nodes and rooted at node $$$1$$$.

Now your task is to count the number of different permutations $$$p$$$ of length $$$n$$$ which satisfies the following condition :

  • For every $$$i(1 \le i \lt n)$$$, either $$$p_i$$$ is an $$$^\dagger$$$ ancestor of $$$p_{i+1}$$$ or $$$p_{i+1}$$$ is an ancestor of $$$p_i$$$.

$$$^\dagger$$$ Node $$$a$$$ is an ancestor of node $$$b$$$ if the shortest path from $$$b$$$ to the root passes through $$$a$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(3 \le n \le 5000)$$$ — the size of the tree.

The next $$$n-1$$$ lines contain two integers $$$x,y$$$ $$$(1 \le x,y \le n, x≠y)$$$ — there is an edge between $$$x$$$ and $$$y$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, print a single integer — the required count modulo $$$10^9 + 7$$$.

Example
Input
2
3
1 3
1 2
5
4 5
1 4
3 1
2 4
Output
2
4
Note

For the first test case, the permutations which satisfies the condition are :

  1. $$$2, 1, 3$$$
  2. $$$3, 1, 2$$$

For the second test case, the permutations which satisfies the condition are :

  1. $$$2, 4, 5, 1, 3$$$
  2. $$$5, 4, 2, 1, 3$$$
  3. $$$3, 1, 5, 4, 2$$$
  4. $$$3, 1, 2, 4, 5$$$