Yevin Kang has a tree with vertices that are labelled with integers from to . A tree is an undirected connected graph that does not contain a cycle.
Let be a positive integer. We define as follows.
For any two vertices , let denote the number of edges on the simple path connecting vertex and vertex . In particular, for all .
A permutation of is good if all of the following conditions are satisfied.
for all .
for all pairs of integers with .
Then, is the number of good permutations.
Yevin thinks this problem is too easy, so he gives you positive integers . He asks you to print the values of , mod .
It may also be useful to note that “mod” corresponds to the operator in most programming languages, indicating the remainder after division. For example, and .
输入格式
Each test has multiple test cases.
The first line of the test contains one integer () — the number of test cases.
The first line of each test case contains two space-separated integers ().
Each of the next lines contains two space-separated integers — indicating that there is an edge connecting and in the tree. It is guaranteed that the edges form a tree.
The next line contains integers, — denoting the queries.
It is guaranteed that the sum of over all test cases in a test (denoted by ) does not exceed .
输出格式
For each test case, output one line with space-separated integers — the values of , mod .
样例
样例输入 1
2
3 3
1 2
1 3
1 2 3
6 3
1 2
1 3
3 4
3 5
3 6
1 2 3
样例输出 1
0 2 2
0 6 12
数据范围与提示
Explanation of Output for Sample Input
The two trees in the sample input are shown below.
:::align{center}
:::
In the first test case, for or , both and are good permutations. is not a good permutation for all values of because
violates the second condition.
It can be shown that no permutation is good for .
In the second test case, is a good permutation for but not a good permutation for because .
The following table shows how the available marks are distributed:
:::