무한 이진 트리 매장

Vasya는 무한 이진 트리 $T$를 하나 가지고 있다. $T$는 다음과 같이 형식적으로 정의된다. $T$에는 무한히 많은 정점이 있고, 정점 번호는 1부터 시작한다. $T$의 각 정점에는 왼쪽 아들과 오른쪽 아들이라는 두 자식이 있다. 정점 $i$의 왼쪽 아들은 정점 $2i$이고, 오른쪽 아들은 정점 $2i+1$이다.

또한 Vasya는 또 다른 이진 트리 $G$를 가지고 있다(다행히도 유한하다). $G$의 모든 정점은 내부 정점이거나 잎이다. 내부 정점에는 왼쪽 아들과 오른쪽 아들이 있고(자식들의 부모라고 부른다), 잎 정점에는 자식이 없다. 모든 정점은 부모를 정확히 하나 가지며, 부모가 없는 정점이 하나 있는데 이 정점을 트리 $G$의 루트라고 부른다.

Vasya는 트리 $G$를 무한 트리 $T$에 매장하려고 한다. 형식적으로 매장은 함수 $f: V(G) \rightarrow V(T)$로 정의된다(여기서 $V(X)$는 트리 $X$의 정점 집합이다). 이 함수는 다음 성질을 만족해야 한다. $G$에서 정점 $v$가 정점 $u$의 왼쪽 아들(또는 오른쪽 아들)이면, $T$에서 정점 $f(v)$는 정점 $f(u)$의 왼쪽 아들(또는 오른쪽 아들)의 부분 트리 안에 있어야 한다.

직관적으로 말하면, 매장은 $G$의 정점들을 $T$ 위의 어딘가에 배치하는 방법이다. 배치된 정점들과 그 자식들 사이에 경로를 그리면, 그림은 일부 간선이 아래로 늘어난 $G$처럼 보인다(이 개념을 더 잘 이해하려면 예제 그림을 보면 도움이 된다).

추가로, Vasya는 각 잎 정점 $v$에 대해 숫자 $h_v$를 정했다. 이는 $v$가 매장되어야 하는 $T$의 정점의 높이이다(정점의 높이는 그 정점과 트리 루트 사이의 간선 수이다). 즉, $G$의 모든 잎 $v$에 대해 $\text{height}(f(v)) = h_v$가 성립해야 한다.

이제 Vasya는 각 잎 $v$가 높이 $h_v$인 정점에 매장되는 $G$의 서로 다른 매장의 수를 알고 싶어 한다. 수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

첫 번째 줄에는 정수 $n$이 주어진다. $n$은 $G$의 정점 수이다($1 \leq n \leq 2000$).

다음 $n$개의 줄은 트리 $G$와 숫자 $h_v$를 설명한다.

$i$번째 정점이 내부 정점이면, $i$번째 줄의 첫 번째 숫자는 $0$이고, 그 뒤에 왼쪽 아들과 오른쪽 아들의 번호가 각각 주어진다.

$i$번째 정점이 잎이면, $i$번째 줄의 첫 번째 숫자는 $1$이고, 그 뒤에 이 잎의 숫자 $h_i$가 주어진다. 모든 $h_i$는 $0 \leq h_i \leq 10^9$를 만족한다.

$G$의 루트는 정점 $1$이다.

조건에 맞는 매장의 수를 $10^9 + 7$로 나눈 나머지를 한 정수로 출력한다.

첫 번째 예제의 가능한 매장 여섯 가지(주의: $G$의 루트가 $T$의 루트와 일치할 필요는 없다):

두 번째 예제의 가능한 매장 열네 가지: