cho.sh

이진 트리 그리기

시간 제한1초메모리 제한512 MB

문제

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$ 인 적당히 큰 정수 $V$를 고정한 후, 아래 규칙에 따라 여러 가지 방법으로 그리는 것을 좋아한다. 편의상 노드 $i$ 의 정수 $x,y$ 좌표 값을 $(x_i, y_i)$ 라 하자.

  1. $1 \le x_i \le V$ 가 되도록 골라야 한다.
  2. 노드 $i$ 가 루트 노드라면 $y_i = -1$ 이어야 한다.
  3. 노드 $p$ 가 노드 $i$의 부모라면 $y_i = y_p - 1$ 이어야 한다.
  4. 루트가 아닌 노드 $i$가 노드 $p$ 의 왼쪽 자식이라면 (즉 $L_p = i$), 반드시 $x_i \lt x_p$ 이며 $i$의 모든 자식 및 자손 노드 $j$에 대해서도 $x_j \lt x_p$ 이어야 한다.
  5. 루트가 아닌 노드 $i$가 노드 $p$ 의 오른쪽 자식이라면 (즉 $R_p = i$), 반드시 $x_i \gt x_p$ 이며 $i$의 모든 자식 및 자손 노드 $j$에 대해서도 $x_j \gt 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$개의 간선, 그리고 고유한 루트가 존재하며 싸이클이 없는 정상적인 이진 트리임이 보장된다.