28080번 - 인경호의 나무

다음은 인하대학교의 나무 소모임 Cool Tree People (CTP) 회원들 사이에 구전으로 내려오는 전설 "인경호의 나무"에 대한 이야기이다.

인경호의 깊은 바닥에는 노드 $N$개로 이루어진 이진 트리가 있다. 각 노드에는 $1$ 이상 $N$ 이하의 고유한 번호가 붙어 있으며, $1$번 노드가 루트 노드이다. 이 트리는 다음과 같은 성질을 만족한다.

• $i$번 노드에는 $1$ 이상 $M$ 이하의 정수 $a_i$가 적혀 있다. $(1 ≤ i ≤ N) $
• 번호가 $k$인 노드의 왼쪽 서브트리에 속하는 모든 노드에는 $a_k$보다 작은 수가 적혀 있다.
• 번호가 $k$인 노드의 오른쪽 서브트리에 속하는 모든 노드에는 $a_k$보다 큰 수가 적혀 있다.

이 전설이 사실인지 확인하기 위해 인경호에 뛰어든 시은이는 놀랍게도 이진 트리를 하나 발견했다! 하지만 트리가 너무 오래된 탓에, 몇 개의 노드에 적힌 수가 지워져 버렸다. 지워진 수의 자리에 다시 $1$ 이상 $M$이하의 정수를 적어, 위 세 가지 성질을 모두 만족하게 하는 방법이 몇 가지인지 알아보자.

첫째 줄에 $N$과 $M$이 공백을 구분으로 주어진다.

다음 $N$개의 줄에 걸쳐 $1 + i$번째 줄에 $i$번 노드의 정보가 주어진다.

노드의 정보는 공백으로 구분된 세 개의 정수로, 순서대로 다음을 뜻한다.

• 첫 번째 정수
  • $1$ 이상 $M$ 이하인 경우 : $i$번 노드에 적힌 수 $a_i$는 해당 정수이다.
  • $-1$인 경우 : $i$번 노드에 적힌 수가 지워졌다.
• 두 번째 정수
  • $1$ 이상 $N$ 이하인 경우 : $i$번 노드는 왼쪽 자식 노드를 가지고 있으며, 그 노드의 번호는 해당 정수이다.
  • $-1$인 경우 : $i$번 노드는 왼쪽 자식 노드를 가지고 있지 않다.
• 세 번째 정수
  • $1$ 이상 $N$ 이하인 경우 : $i$번 노드는 오른쪽 자식 노드를 가지고 있으며, 그 노드의 번호는 해당 정수이다.
  • $-1$인 경우 : $i$번 노드는 오른쪽 자식 노드를 가지고 있지 않다.

지문의 조건을 만족하도록 지워진 수의 자리에 정수를 채워 넣는 방법이 몇 가지인지 출력한다.

방법이 너무 많을 수도 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

• $1 ≤ N ≤ 1\,000$
• $N ≤ M ≤ 2\,000$
• 올바른 이진 트리만 입력으로 주어진다.
• 지워진 수가 하나도 없거나 답이 $0$인 경우는 주어지지 않는다.