이진 트리

문제

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

$T$ 에서 노드 $u$ 를 루트로 하는 서브 트리는, $u$ 와 $u$ 의 자손 노드들로만 구성된 집합이다.
$T$ $T$ 의 중위 순회 수열 $p (T)$ $p (T)$ 는 $T$ $T$ 를 중위 순회하면서 방문하는 노드들을 순서대로 나열한 수열로, 아래와 같이 정의할 수 있다.
- $T$ 의 루트 노드를 $r$ 이라 하자. $[r]$ 을 $r$ 하나로만 구성된 길이 $1$ 의 수열이라고 하자.
- 만약 $r$ 의 자식 노드가 $0$ 개라면, $p (T)$ 는 $[r]$ 이다.
- 만약 $r$ 의 자식 노드가 $2$ 개라면, $r$ 의 왼쪽 자식 노드를 루트로 하는 서브 트리가 $X$ , $r$ 의 오른쪽 자식 노드를 루트로 하는 서브 트리가 $Y$ 일 때, $p (T)$ 는 $p (X)$ , $[r]$ , $p (Y)$ 을 순서대로 이어붙인 수열이다.
$T$ 의 리프 노드 개수를 $k$ 라고 하자. $T$ 의 리프 노드들에 $1, 2, \cdots , k$ 의 번호를 $p (T)$ 에서 나타나는 순서대 로 (즉, 중위 순회 방문 순서대로) 붙였다고 하자.
$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$ 로 나눈 나머지이다.

예를 들어, 다음과 같은 이진 트리 $T$ 가 있다고 가정해보자.


(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$ 개인 트리
$T_{i}$ 는 루트의 왼쪽 자식 노드를 루트로 하는 서브 트리가 $T_{A_i}$ 이고, 루트의 오른쪽 자식 노드를 루트로 하는 서브 트리가 $T_{B_i}$ 인 트리 ( $1 ≤ i ≤ N$ , $0 ≤ A_i ≤ i - 1$ , $0 ≤ B_i ≤ i - 1$ )

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

입력

첫 번째 줄에 정수 $N$ 이 주어진다.

다음 $N$ 개의 줄 중 $i$ ( $1 ≤ i ≤ N$ )번째 줄에는 $A_{i}$ 와 $B_{i}$ 가 공백으로 구분되어 주어진다.

출력

$N$ 개의 줄을 출력한다. $i$ ( $1 ≤ i ≤ N$ )번째 줄에는 $S (T_{i})$ 를 출력해야 한다.

문제

입력

출력

예제

예제 1

예제 2