모든 노드의 자식 노드가 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, r의 오른쪽 자식 노드를 루트로 하는 서브 트리가 Y일 때, p(T)는 p(X), [r], p(Y)을 순서대로 이어붙인 수열이다.
T의 리프 노드 개수를 k라고 하자. T의 리프 노드에 1,2,\dots,k의 번호를 p(T)에서 나타나는 순서대로 (즉, 중위 순회 방문 순서대로) 붙였다고 하자.
T의 서브 트리를 선택하면 해당 서브 트리에 포함된 리프 노드들이 덮인다고 하자.
1 \le a \le b \le k일 때, f(a,b)는 리프 노드들 중 번호가 a 이상 b 이하인 리프 노드들만을 덮고 다른 리프 노드들은 덮지 않기 위해, T에서 선택해야하는 최소 서브 트리 개수이다.
S(T)의 값은 1 \le a \le b \le k인 모든 (a,b) 정수 순서쌍에 대한 f(a,b)의 합을 10^9+7로 나눈 나머지이다.

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

f(5,7)의 값은 2이다. 다음과 같이 서브 트리 두 개를 선택하여 5,6,7번 리프 노드만 덮이기 때문이다.

이런 식으로 모든 1 \le a \le b \le 7에 대해 f(a,b)의 값의 합은 47이고, 이를 10^9+7로 나눈 나머지를 구하면 S(T)=47이다.

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

이진 트리 T_1,T_2,...,T_N을 다음과 같이 정의한다.

T_0은 노드가 1개인 트리
T_i는 루트의 왼쪽 자식 노드를 루트로 하는 서브 트리가 T_{A_i}이고, 루트의 오른쪽 자식 노드를 루트로 하는 서브 트리가 T_{B_i}인 트리(1 \le i \le N, 0 \le A_i \le i-1, 0 \le B_i \le i-1)

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

[제약 조건]

이진 트리 timer 2초 memory 1024MB

이진 트리 2초 1024MB