在一个平行宇宙中，所有人在 CCO 中都获得了满分。因此，Troy 需要通过抽奖来选出获胜者。每位参赛者将选择数字来创建一张彩票。彩票是一个大小为 $N$ 的数组，索引从 $1$ 到 $N$，其中每个条目都是一个 $0$ 到 $K$ 之间的数字。
获胜彩票是通过将 $K$ 个球（编号从 $1$ 到 $K$）以随机顺序投入一棵有根二叉树来确定的。该树有 $N$ 个节点（编号从 $1$ 到 $N$），根节点为 $1$。
每个球都有一个指定的投入节点。当一个球被投入到一个未被占用的节点或进入一个未被占用的节点时，会发生以下三种情况之一：
- 如果当前节点的所有子节点都被球占用（或者该节点没有子节点），则当前球停留在当前节点。也就是说，它保持不动，不再移动。
- 如果当前节点只有一个未被占用的子节点，则当前球将移动到该子节点。
- 如果当前节点有两个未被占用的子节点，且当前球是刚被投入的，它可以向左或向右移动。否则，它将继续沿其之前的移动方向移动。
如果所有 $K$ 个球无法全部投入，则无法确定获胜彩票。这种情况发生在当一个球被投入时，其投入节点已被另一个球占用。
如果所有 $K$ 个球都已投入，球的停留位置决定了获胜彩票。获胜彩票的第 $i$ 个条目是停留在节点 $i$ 的球的编号，如果节点 $i$ 没有球停留，则为 $0$。
Troy 想知道可能的获胜彩票数量（数量可能为零）。
输入格式
第一行包含两个空格分隔的整数 $N$ 和 $K$，分别表示二叉树的节点数和球的数量。
下一行包含 $K$ 个空格分隔的整数，其中第 $i$ 个整数表示编号为 $i$ 的球的指定投入节点。
接下来的 $N$ 行，每行包含两个空格分隔的整数。第 $i$ 行包含 $L_i$ 和 $R_i$，分别表示第 $i$ 个节点的左子节点和右子节点，其中 $0$ 表示不存在该子节点。
子任务
| 分值 | $N$ 的范围 | $K$ 的范围 | 附加约束 |
|---|---|---|---|
| 3 分 | $1 \le N \le 12$ | $1 \le K \le 6$ | 无 |
| 4 分 | $1 \le N \le 4000$ | $1 \le K \le 4000$ | 所有节点都没有左子节点 |
| 9 分 | $1 \le N \le 4000$ | $1 \le K \le 4000$ | $N$ 个投入节点各不相同 |
| 9 分 | $1 \le N \le 4000$ | $1 \le K \le 4000$ | 无 |
输出格式
输出获胜彩票数量除以 $10^9 + 7$ 的余数。
样例
输入格式 1
5 2 1 3 2 3 0 0 4 5 0 0 0 0
输出格式 1
4
说明
树的结构如下：
考虑先投入球 1 的情况。如果球 1 向左走，它将停留在节点 2。之后，投入球 2，它可以停留在节点 4 或 5。如果球 1 向右走，它将停留在节点 5。然后，球 2 将停留在节点 4。
考虑先投入球 2 的情况。球 2 可以向左或向右走，分别停留在节点 4 或 5。然后，如果球 1 在投入后向左移动，它将停留在节点 2。然而，如果球 1 向右移动，它将停留在节点 4 或 5 中球 2 未占用的那个位置。
可能的获胜彩票为 $[0, 1, 0, 2, 0], [0, 1, 0, 0, 2], [0, 0, 0, 1, 2]$ 和 $[0, 0, 0, 2, 1]$。
输入格式 2
4 3 1 2 4 0 2 0 3 0 4 0 0
输出格式 2
2
说明
树的结构如下：
此测试用例满足第二个子任务。
球 3 必须首先被投入，因为如果球 1 或球 2 在球 3 之前被投入，它会停留在节点 4，这将导致球 3 无法被投入。
因此，我们可以先投入球 3，然后是球 2，最后是球 1；或者我们可以先投入球 3，然后是球 1，最后是球 2。
可能的获胜彩票为 $[0, 1, 2, 3]$ 和 $[0, 2, 1, 3]$。
形式化定义
二叉树是一组节点，它要么为空，要么是一个根节点加上左子树和右子树，其中左子树和右子树也都是二叉树。给定一个节点 $x$，如果其左子树不为空，则该子树的根被称为 $x$ 的左子节点。类似地，给定一个节点 $x$，如果其右子树不为空，则该子树的根被称为 $x$ 的右子节点。