이진 트리

모든 노드의 자식 노드가 $0$개 또는 $2$개인 이진 트리 $T$에 대해 $S(T)$를 다음과 같이 정의한다.

• $T$에서 노드 $u$를 루트로 하는 서브 트리는 $u$와 $u$의 자손 노드로만 이루어진 집합이다.
• $T$의 중위 순회 수열 $p(T)$는 $T$를 중위 순회하며 방문한 노드를 순서대로 나열한 수열이다. 다음과 같이 재귀적으로 정의한다.
  • $T$의 루트 노드를 $r$이라 하자. $[r]$은 $r$ 하나로만 이루어진 길이 $1$의 수열이다.
  • $r$의 자식 노드가 $0$개이면 $p(T)$는 $[r]$이다.
  • $r$의 자식 노드가 $2$개이면, $r$의 왼쪽 자식을 루트로 하는 서브 트리를 $X$, 오른쪽 자식을 루트로 하는 서브 트리를 $Y$라 할 때 $p(T)$는 $p(X)$, $[r]$, $p(Y)$를 순서대로 이어 붙인 수열이다.
• $T$의 리프 노드 개수를 $k$라 하자. $T$의 리프 노드에 $p(T)$에 나타나는 순서대로, 즉 중위 순회 방문 순서대로 $1, 2, \cdots, k$의 번호를 붙인다.
• $T$의 서브 트리를 선택하면, 그 서브 트리에 포함된 리프 노드가 덮인다고 한다.
• $1 ≤ a ≤ b ≤ k$일 때, $f(a, b)$는 번호가 $a$ 이상 $b$ 이하인 리프 노드만 덮고 나머지 리프 노드는 덮지 않도록 $T$에서 선택해야 하는 서브 트리의 최소 개수이다.
• $S(T)$는 $1 ≤ a ≤ b ≤ k$인 모든 정수 순서쌍 $(a, b)$에 대한 $f(a, b)$의 합을 $10^9+7$로 나눈 나머지이다.

(a)는 정의에 따라 만든 트리이다. (b)는 같은 트리의 리프 노드에 번호를 붙인 모습이다.

$f(5, 7)$의 값은 $2$이다. 아래 그림처럼 서브 트리 두 개를 선택하면 $5$, $6$, $7$번 리프 노드만 덮인다.

$1 ≤ a ≤ b ≤ 7$인 모든 $f(a, b)$의 합은 $47$이다. 이를 $10^9 + 7$로 나눈 나머지를 구하면 $S(T) = 47$이다.

정수열 $A_1, A_2, \cdots, A_N$과 $B_1, B_2, \cdots, B_N$이 주어진다.

이진 트리 $T_0, T_1, \cdots, T_N$을 다음과 같이 정의한다.

• $T_0$은 노드가 1개인 트리이다.
• $1 ≤ i ≤ N$일 때 $T_i$는 루트의 왼쪽 자식을 루트로 하는 서브 트리가 $T_{A_i}$이고, 루트의 오른쪽 자식을 루트로 하는 서브 트리가 $T_{B_i}$인 트리이다 ($0 ≤ A_i ≤ i - 1$, $0 ≤ B_i ≤ i - 1$).

$S(T_1), S(T_2), \cdots, S(T_N)$을 구하는 프로그램을 작성하라.

첫 번째 줄에 정수 $N$이 주어진다. 다음 $N$개의 줄 중 $i$번째 줄에는 $A_i$와 $B_i$가 공백으로 구분되어 주어진다.

$N$개의 줄을 출력한다. $i$번째 줄에는 $S(T_i)$를 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 ≤ N ≤ 100\,000$
• $0 ≤ A_i ≤ i - 1$ ($1 ≤ i ≤ N$)
• $0 ≤ B_i ≤ i - 1$ ($1 ≤ i ≤ N$)