Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a tree with $N$ nodes (numbered $1$ through $N$), rooted at node $1$. For each valid $i$, node $i$ has a value $a_{i}$ written on it.

An undirected simple path between any two nodes $u$ and $v$ is said to be vertical if $u=v$ or $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$. Let's define a vertical partition of the tree as a set of vertical paths such that each node belongs to exactly one of these paths.

You are also given a sequence of $N$ integers $b_{1}, b_{2}, \ldots, b_{N}$. A vertical partition is good if, for each of its paths, we can permute the values written on the nodes in this path, and this can be done in such a way that we reach a state where for each valid $i$, the value written on node $i$ is $b_{i}$.

The difficulty of your task is described by a parameter $S$. If $S=1$, your task is only to determine whether at least one good vertical partition exists. If $S=2$, you are required to find the number of good vertical partitions modulo $1,000,000,007$ ($10^{9}+7$).

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $S$.
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that nodes $u$ and $v$ are connected by an edge.
The next line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.
The line after that contains $N$ space-separated integers $b_{1}, b_{2}, \ldots, b_{N}$.

------ Output ------
For each test case, print a single line containing one integer:
If $S=1$, this integer should be $1$ if a good vertical partition exists or $0$ if it does not exist.
If $S=2$, this integer should be the number of good vertical partitions modulo $1,000,000,007$ ($10^{9}+7$).

------ Constraints ------
$1 ≤ T ≤ 10^{6}$
$1 ≤ N ≤ 10^{5}$
$S \in \{1, 2\}$
$1 ≤ u, v ≤ N$
the graph described on the input is a tree
$1 ≤ a_{i}, b_{i} ≤ 10^{6}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------ Subtasks ------
Subtask #1 (40 points, time limit 1 seconds): the sum of $N$ over all test cases does not exceed $1,000$

Subtask #2 (30 points, time limit 2 seconds): $S = 1$

Subtask #3 (30 points, time limit 2 seconds): original constraints

----- Sample Input 1 ------
4

3 2

1 2

2 3

4 5 6

4 6 5

6 2

1 2

1 3

2 4

3 5

3 6

10 20 30 40 50 60

10 40 50 20 30 60

6 1

1 2

1 3

2 4

3 5

3 6

10 20 30 40 50 60

10 40 50 20 30 60

1 2

1

2
----- Sample Output 1 ------
2

3

1

0
----- explanation 1 ------
Example case 1: The good vertical partitions are $\{[1], [2, 3]\}$ and $\{[1, 2, 3]\}$.

Example case 2: The good vertical partitions are:
- $\{[1, 2, 4], [3, 5], [6]\}$
- $\{[1], [2, 4], [3, 5], [6]\}$
- $\{[1, 3, 5], [2, 4], [6]\}$

Example case 3: The same as example case 2, but with $S=1$.

Example case 4: There is no good vertical partition.

见题面

见题面