Drawing Binary Trees

Bert has recently become fascinated with binary trees. For a tree to be a binary tree, each node may have at most 2 children. For convenience, the nodes of a binary tree $T$ are numbered 1 through $N$. The left child of node $i$ is written $L\_i$, and the right child is written $R\_i$. If a node has no child on that side, the value is 0.

The tree below has $N = 3$, $L = [2, 0, 0]$, and $R = [3, 0, 0]$. Its root is node 1.

Bert likes to draw binary trees. He first fixes an integer $V \ge N$ that is large enough, then draws the tree in several ways by the rules below. Let the integer coordinates of node $i$ be $(x_i, y_i)$.

1. Choose $x_i$ so that $1 \le x_i \le V$.
2. If node $i$ is the root, then $y_i = -1$.
3. If node $p$ is the parent of node $i$, then $y_i = y_p - 1$.
4. If a non-root node $i$ is the left child of node $p$ (that is, $L_p = i$), then $x_i < x_p$ must hold. Also, $x_j < x_p$ must hold for every child and descendant $j$ of $i$.
5. If a non-root node $i$ is the right child of node $p$ (that is, $R_p = i$), then $x_i > x_p$ must hold. Also, $x_j > x_p$ must hold for every child and descendant $j$ of $i$.

When $N$ coordinates satisfy all the rules above, the binary tree can be drawn. Two drawings are different if any node has a different $x$ coordinate in them. Under these rules, every node has the same $y$ coordinate in every drawing.

For the example above with $V = 4$, the tree can be drawn in 4 different ways, as shown below.

Given any binary tree, Bert wondered how many different drawings follow all of the rules above. Alice saw this and called that problem too easy, so she gave him a new one.

• If the $x$ coordinates of some of the $N$ nodes (possibly none, possibly all) are fixed, how many different drawings are possible when the rules above are followed?
• Specifically, an integer array $A$ is given. If $A_i = 0$, the $x$ coordinate of node $i$ is not fixed. If $A_i \in [1, V]$, then the $x$ coordinate of node $i$ must be exactly $x_i = A_i$.

For example, if $A = [0, 1, 0]$, the tree can be drawn in the 3 leftmost ways among the 4 drawings above, which are the ones with $x_2 = 1$. For the same tree with $A = [1, 0, 0]$, there is no valid drawing. The tree can be drawn in 4 ways as shown above, but none of them has $x_1 = 1$.

Given $N$, $V$, and three integer arrays $A$, $L$, and $R$, count the number of ways to draw the binary tree that satisfy Alice's conditions.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$ and $V$, separated by a space. The second line contains the array $A$, the third line contains the array $L$, and the fourth line contains the array $R$. Each array is given as $N$ integers separated by spaces.

For each test case, print the answer on its own line. The answer can be very large, so print the remainder when it is divided by $444\,449$.

• $1 \le T \le 10$
• $1 \le N \le 100\,000$
• $N \le V \le 1\,000\,000\,000$
• For every $i$ with $1 \le i \le N$:
  • $0 \le A_i \le V$
  • $0 \le L_i, R_i \le N$
• The input binary tree has $N$ nodes and $N-1$ edges, has a unique root, and contains no cycles. This is guaranteed.