Nam draws a tree in a paper (Note: tree here is a sinple connected acyclic graph in Graph theory, not tree in reality). The tree consists of N nodes. Nam want to makes his tree more beautiful. Therefore, he decided to coloring all N nodes.
Nam numbering nodes from 1 to N for convinent. He firstly color node 1. Then he will color N - 1 remaining nodes, in any order which satisfied condition: node are chosen to color must be adjacent to one of nodes colored before. Two nodes are consider adjacent if there is a direct edge between them.
Nam wondering, how many ways of coloring the tree he possible make. Two ways are consider different if order of coloring nodes in 2 ways are different, because Nam uses only 1 color.
Input
The first line is T - the number of test cases. Then T test cases follow.
Each test consists of several lines.
- The first line is N - the number of nodes in tree.
- Then the next N - 1 lines, each line contains 2 integer u and v (1 ≤ u, v ≤ N), denoting there is a direct edge between node u and node v. It is guaranteed that these edges form a tree.
Output
For each test, print the number of ways coloring the tree in a single line. Since this number can very large, you must print it modulo 109 + 7.
Constraints
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100000
In the first test, there is only 1 order of coloring the tree, that is (1, 2, 3). In the second test, there are 2 orders of coloring the tree, they are (1, 2, 3) and (1, 3, 2). In the third test, there are 3 orders of coloring the tree, they are (1, 2, 3, 4), (1, 2, 4, 3) and (1, 4, 2, 3).
