이진 트리 그리기

Bert는 최근 이진 트리(Binary Tree)의 매력에 푹 빠져 있다. 어떤 트리가 이진 트리이려면 각 노드의 자식이 최대 2개여야 한다. 편의상 이진 트리 $T$의 노드는 1번부터 $N$번까지 번호가 붙어 있으며, $i$번 노드의 왼쪽 자식은 $L\_i$, 오른쪽 자식은 $R\_i$로 표현한다. 해당 방향에 자식이 없으면 이 값은 0이다.

아래 트리는 $N = 3$, $L = [2, 0, 0]$, $R = [3, 0, 0]$인 경우를 나타내며, 이 트리의 루트는 1번 노드이다.

Bert는 이진 트리 그리기를 좋아한다. 먼저 충분히 큰 정수 $V \ge N$을 고정한 뒤, 아래 규칙에 따라 여러 가지 방법으로 트리를 그린다. 노드 $i$의 정수 좌표를 $(x_i, y_i)$라 하자.

1. $1 \le x_i \le V$가 되도록 $x_i$를 골라야 한다.
2. 노드 $i$가 루트라면 $y_i = -1$이어야 한다.
3. 노드 $p$가 노드 $i$의 부모라면 $y_i = y_p - 1$이어야 한다.
4. 루트가 아닌 노드 $i$가 노드 $p$의 왼쪽 자식이라면($L_p = i$), 반드시 $x_i < x_p$이어야 하며, $i$의 모든 자식 및 자손 노드 $j$에 대해서도 $x_j < x_p$이어야 한다.
5. 루트가 아닌 노드 $i$가 노드 $p$의 오른쪽 자식이라면($R_p = i$), 반드시 $x_i > x_p$이어야 하며, $i$의 모든 자식 및 자손 노드 $j$에 대해서도 $x_j > x_p$이어야 한다.

위 조건을 모두 만족하는 $N$개의 좌표를 정하면 이진 트리를 그릴 수 있다고 한다. 두 그림에서 같은 노드의 $x$ 좌표 값이 다르면 두 그림은 다른 방법으로 그려진 것이다. (위 규칙을 따르면 각 노드의 $y$ 좌표 값은 항상 같다.) 위 트리에서 $V = 4$라면 아래와 같은 4가지 방법으로 그릴 수 있다.

Bert는 임의의 이진 트리가 주어졌을 때 위 방법을 모두 지키면서 몇 가지 다른 방법으로 그릴 수 있는지 궁금해졌다. 이를 지켜보던 Alice는 그 문제는 너무 쉽다며 새로운 문제를 냈다.

• $N$개의 노드 중 일부 노드(0개일 수도 있고 $N$개일 수도 있다)의 $x$ 좌표를 고정한 뒤 위 규칙에 따라 그린다면, 몇 가지 다른 방법으로 그릴 수 있을까?
• 구체적으로 정수 배열 $A$가 주어진다. $A_i = 0$이면 노드 $i$의 좌표는 고정되지 않은 것이고, $A_i \in [1, V]$이면 노드 $i$의 좌표는 반드시 $x_i = A_i$가 되어야 한다.

예를 들어 $A = [0, 1, 0]$이면, 앞서 본 4개의 트리 중 $x_2 = 1$을 만족하는 왼쪽 3가지 방법으로 그릴 수 있다. 같은 트리에 대해 $A = [1, 0, 0]$이면 조건을 만족하며 그릴 방법이 없다. 앞서 본 대로 4가지 방법으로 그릴 수는 있지만, $x_1 = 1$인 경우는 불가능하다.

입력으로 $N$, $V$와 세 정수 배열 $A$, $L$, $R$이 주어졌을 때, Alice의 조건을 만족하며 이진 트리를 그릴 수 있는 방법의 수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $V$가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$가, 셋째 줄에는 배열 $L$이, 넷째 줄에는 배열 $R$이 주어진다. 각 줄의 배열은 공백으로 구분된 $N$개의 정수이다.

각 테스트 케이스의 정답을 한 줄에 하나씩 출력한다. 수가 매우 클 수 있으므로 $444\,449$로 나눈 나머지를 출력한다.

• $1 \le T \le 10$
• $1 \le N \le 100\,000$
• $N \le V \le 1\,000\,000\,000$
• $1 \le i \le N$인 $i$에 대하여
  • $0 \le A_i \le V$
  • $0 \le L_i, R_i \le N$
• 입력으로 주어지는 이진 트리는 $N$개의 노드, $N-1$개의 간선을 가지며, 고유한 루트가 존재하고 사이클이 없는 정상적인 이진 트리임이 보장된다.