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 10⁹ + 7.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100000