Problem Description

In a parallel universe, everyone has achieved a perfect score at CCO. Consequently, Troy needs to select winners through a lottery. Each participant will choose some numbers to create a lottery ticket. A lottery ticket is an array of size $N$, numbered from $1$ to $N$, where each element is a number from $0$ to $K$.

The winning ticket is determined by randomly placing $K$ balls (numbered from $1$ to $K$) into a rooted binary tree in random order. This tree has $N$ nodes (numbered from $1$ to $N$), with node $1$ as the root.

Each ball has a designated node where it will be placed. When a ball is placed in an empty node or enters an empty node, one of the following three scenarios occurs:

1. If all child nodes of the current node are occupied (or if the node has no children), the current ball will stay at the current node.
2. If the current node has only one empty child node, the current ball will move to that child node.
3. If the current node has two empty child nodes, and if the current ball has just been placed, it can move left or right. Otherwise, it will continue moving in its previous direction.

If not all $K$ balls can be placed, there is no determined winning ticket. This happens when a ball is placed and its designated node is already occupied by another ball.

If all $K$ balls are placed, the positions of the balls determine the winning ticket. The $i$-th element of the winning ticket is the number of the ball that stays at node $i$, or $0$ if no ball stays at node $i$.

Troy wants to know the number of possible winning tickets. Since the answer could be very large, you only need to find the result modulo $10^9+7$.

Input Format

The first line contains two space-separated integers $N$ and $K$, representing the number of nodes in the binary tree and the number of balls, respectively.

The second line contains $K$ space-separated integers, where the $i$-th integer represents the designated node for the ball numbered $i$.

The last $N$ lines, each containing two space-separated integers, describe the left and right child nodes of each node. The $i$-th line contains $L_i$ and $R_i$, where $0$ indicates that the child node does not exist.

Output Format

Output the number of winning tickets modulo $10^9+7$.

Sample Input and Output

Sample Input #1

5 2
1 3
2 3
0 0
4 5
0 0
0 0

Sample Output #1

4

Sample Input #2

4 3
1 2 4
0 2
0 3
0 4
0 0

Sample Output #2

2

Notes/Hints

Sample 1 Explanation

Consider when ball $1$ is placed first. If ball $1$ moves left, it will stay at node $2$. Afterwards, ball $2$ can be placed at node $4$ or $5$. If ball $1$ moves right, it will stay at node $5$. Then, ball $2$ will stay at node $4$.

Consider when ball $2$ is placed first. Ball $2$ can move left or right, staying at node $4$ or $5$ respectively. Then, if ball $1$ moves left after being placed, it will stay at node $2$. However, if ball $1$ moves right, it will stay at node $4$ or $5$, depending on the position not occupied by ball $2$.

Possible winning tickets are $[0,1,0,2,0]$, $[0,1,0,0,2]$, $[0,0,0,1,2]$, and $[0,0,0,2,1]$.

Sample 2 Explanation

Ball $3$ must be placed first because if ball $1$ or ball $2$ is placed before ball $3$, it will stay at node $4$, preventing ball $3$ from being placed.

Thus, we can place ball $3$ first, then place ball $2$, and finally place ball $1$, or we can place ball $3$ first, then place ball $1$, and finally place ball $2$. The corresponding winning tickets are $[0,1,2,3]$ and $[0,2,1,3]$.

Data Range

For all data, $1 \leq N, K \leq 4000$.

见题面 Input 部分

见题面 Output 部分