A. Control of Randomness

You are given a tree with vertices.

Let's place a robot in some vertex , and suppose we initially have coins. Consider the following process, where in the -th step (starting from ):

• If is odd, the robot moves to an adjacent vertex in the direction of vertex ;
• Else, is even. You can either pay one coin (if there are some left) and then the robot moves to an adjacent vertex in the direction of vertex , or not pay, and then the robot moves to an adjacent vertex chosen uniformly at random.

The process stops as soon as the robot reaches vertex . Let be the minimum possible expected number of steps in the process above if we spend our coins optimally.

Answer queries, in the -th of which you have to find the value of , modulo .

Formally, let . It can be shown that the answer can be expressed as an irreducible fraction , where and are integers and . Output the integer equal to . In other words, output such an integer that and .

Each test contains multiple test cases. The first line contains the number of test cases ( ). The description of the test cases follows.

The first line of each test case contains two integers and ( ; ) — the number of vertices in the tree and the number of queries.

The next lines contain the edges of the tree, one edge per line. The -th line contains two integers and ( ; ), denoting the edge between the nodes and .

The next lines contain two integers and ( ; ).

It's guaranteed that the given edges form a tree.

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

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

For each test case, print integers: the values of modulo .

Formally, let . It can be shown that the answer can be expressed as an irreducible fraction , where and are integers and . Output the integer equal to . In other words, output such an integer that and .

输入 #1

2
4 4
1 2
2 3
2 4
2 0
3 0
4 0
3 1
12 10
1 2
2 3
2 4
1 5
5 6
6 7
6 8
6 9
8 10
10 11
10 12
6 0
9 0
10 0
11 0
3 1
7 1
10 1
12 1
12 2
11 12

输出 #1

1
6
6
2
4
9
8
15
2
3
6
9
5
5

The tree in the first test case:

In the first query, the expected value is equal to , since the robot starts moving from vertex to vertex in the first step and the process stops.

Let's calculate the expected value in the second query ( is the number of steps):

• , the distance to vertex is and the robot cannot reach it in fewer steps.
• , since there is only one sequence of steps leading to . This is with probability .
• , since the robot can reach vertex by only taking an even number of steps.
• : possible paths .
• : possible paths .
• in the general case.

As a result, .

The tree in the second test case: