Problem Description

Kazari is learning depth-first search. More precisely, she is doing an experiment about it.
Consider an unrooted tree with $n$ vertices and an empty array called $A$.
She randomly chooses a vertex $s$ as root and starts from $s$ to walk around, following the rules below.
* When she enters a vertex $x$ for the first time, she append $x$ to $A$ at once.
* If some adjacent vertex has not been visited, she randomly chooses one and walks into it.
* If all adjacent vertices have been visited,
* If she is at root, the experiment is done.
* If she is not at root, she walks into the vertex which is the most nearest to root.
Among all possible arrays that $A$ is likely to be finally, Kazari wishes to count how many of them is lexicographically smaller than the given array $B$. Since the answer is too large, print it modulo $10 ^ 9 + 7$.

Input

The first line of the input contains an integer $T$ denoting the number of test cases.
Each test case starts with a positive integer $n$ $(\sum{n} \le 10 ^ 6)$, denoting the number of vertices.
The second line contains $n$ integers $B_1, B_2, ..., B_n$ $(1 \le B_i \le n, \forall i \neq j, B_i \neq B_j)$.
Each of next $n - 1$ lines contains two integers $u, v$, representing an edge $(u, v)$ on the tree.

Output

For each test case, print a non-negative integer denoting the answer modulo $10 ^ 9 + 7$.

2					
5					
2 1 3 5 4	
1 2				
2 3				
2 4				
4 5				
6		
6 4 5 3 2 1
1 2				
2 3				
3 4				
4 5				
5 6				

3
9