Counting Winning Lottery Tickets

In a parallel universe everyone scores full marks at CCO, so Troy needs to choose the winners by lottery. In this lottery, each contestant picks some numbers to create a lottery ticket. A lottery ticket is represented by an array of size N (indexed from 1 to N) and each element is an integer between 0 and K inclusive.

The winning lottery ticket is determined by the following process. There is a rooted binary tree with N nodes (numbered 1 to N), with node 1 as the root. There are K balls, numbered 1 to K. Each ball has a designated drop node. The balls are thrown in a random order. When a ball is thrown, it is dropped at its designated drop node. At any node, if the node is empty the ball will enter it and then follow these rules:

• If the current node has no children or if all of its existing children are occupied by balls, then the ball stops at the current node.
• If the current node has exactly one empty child, then the ball moves to that child.
• If the current node has two empty children then
  • If the ball has just been dropped (i.e. it has not moved before), it can choose either the left or the right child. (Formally, if the two children are L and R, the ball may move to L or R.)
  • If the ball is already in motion (i.e. it has moved in a previous step), then it continues in the same direction that it chose initially.

If at any point a ball is to be dropped onto a node that is already occupied by another ball, the process is invalid and there is no winning lottery ticket. However, if all K balls are successfully dropped, the final positions of the balls determine the winning lottery ticket. The i-th element of the ticket is the number of the ball that stopped at node i, or 0 if no ball stopped there.

Troy wants to know how many distinct winning lottery tickets are possible, considering all possible valid orders of ball dropping as well as all choices the balls can make when they are dropped into a node with two available children. Since the answer might be huge, output it modulo \(10^9+7\).

Input Format: The input will describe a binary tree, the designated drop nodes for each ball, and the numbers N and K as follows.

inputFormat

The first line contains two integers N and K (1 ≤ N, K ≤ 10), representing the number of nodes in the tree and the number of balls respectively.

The next N lines each contain two integers L and R (0 ≤ L, R ≤ N). For the i-th of these lines, L and R are the indices of the left and right child of node i respectively (a value of 0 indicates that the child does not exist). It is guaranteed that the tree is a valid rooted binary tree with node 1 as the root.

The last line contains K integers. The i-th integer is the designated drop node for ball i (1 ≤ designated drop node ≤ N).

outputFormat

Output a single integer: the number of distinct winning lottery tickets possible modulo \(10^9+7\>.

sample

3 1
2 3
0 0
0 0
1

2