이진 트리 timer 2초 memory 1024MB

모든 노드의 자식 노드가 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)을 구하는 프로그램을 작성하라.

[제약 조건]

• 주어지는 모든 수는 정수이다.

• 1 \le N \le 100,000

• 0 \le A_i \le i-1 (1 \le i \le N)

• 0 \le B_i \le i-1 (1 \le i \le N)