K. MEX
time limit per test
5 seconds
memory limit per test
1024 MB
input
standard input
output
standard output

You are given an undirected tree with $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$. Each node $$$i$$$ on the tree has a weight $$$p_i$$$. It is guaranteed that the weights $$$p_1, p_2, \dots, p_n$$$ form a permutation.

For a connected component on the tree (that is, a connected subgraph consisting of some nodes of the tree and the edges between them), we define its MEX value as the smallest non-negative integer that does not appear in the set of node weights within this connected component.

Now there are $$$q$$$ queries. Each query gives two integers $$$A$$$ and $$$B$$$. For each query, you need to determine how many connected components in the tree satisfy both of the following conditions:

  1. The connected component contains node $$$A$$$.
  2. The MEX value of the connected component is exactly $$$B$$$.

Since the number of connected components satisfying the conditions may be very large, output the answer to each query modulo $$$10^9 + 7$$$.

  • Permutation: If a sequence of length $$$n$$$ contains every integer from $$$0$$$ to $$$n-1$$$ exactly once, then it is called a permutation of $$$0$$$ to $$$n-1$$$. For example, $$$[2, 0, 3, 1]$$$ is a permutation, while $$$[0, 1, 1, 3]$$$ is not.
Input

The input contains multiple test cases.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), denoting the number of test cases.

For each test case, the first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \lt n$$$). It is guaranteed that these numbers form a permutation of $$$0$$$ to $$$n-1$$$.

The next $$$n - 1$$$ lines each contain two integers $$$u, v$$$ ($$$1 \le u, v \le n$$$), representing an edge in the tree.

The following $$$q$$$ lines each contain two integers $$$A, B$$$ ($$$1 \le A \le n, 0 \le B \le n$$$), representing a query.

It is guaranteed that for each test file, the sum of all $$$n$$$ and the sum of all $$$q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$, respectively.

Output

For each test case, output $$$q$$$ lines. Each line should contain one integer, representing the answer to the corresponding query modulo $$$10^9 + 7$$$.

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

In the first sample:

  • For the first query ($$$A=2, B=0$$$): node $$$2$$$ has weight $$$0$$$. Any connected component containing node $$$2$$$ must have MEX value greater than $$$0$$$, so there is no connected component satisfying the conditions.
  • For the second query ($$$A=4, B=1$$$): any connected component satisfying the conditions must contain node $$$4$$$ and node $$$2$$$ (whose weight is $$$0$$$), but must not contain node $$$3$$$ (whose weight is $$$1$$$). Since the unique path connecting node $$$4$$$ and node $$$2$$$ in the tree must pass through node $$$3$$$, it is impossible to construct such a valid connected component.
  • For the third query ($$$A=4, B=2$$$): the connected components satisfying the conditions are $$$\{2, 3, 4\}$$$ and $$$\{2, 3, 4, 5\}$$$. Both have MEX value $$$2$$$ and both contain node $$$4$$$, so there are $$$2$$$ valid choices.
  • For the fourth query ($$$A=1, B=3$$$): the connected components satisfying the conditions are $$$\{1, 2, 3\}$$$ and $$$\{1, 2, 3, 5\}$$$, so there are $$$2$$$ valid choices.