Binary Tree

For a binary tree $T$ in which every node has either $0$ or $2$ children, $S(T)$ is defined as follows.

• In $T$, the subtree rooted at node $u$ consists of $u$ and the descendants of $u$.
• The inorder sequence $p(T)$ of $T$ is the sequence of nodes in the order they are visited by an inorder traversal of $T$. It is defined recursively.
  • Let $r$ be the root of $T$. $[r]$ is the sequence of length $1$ that contains only $r$.
  • If $r$ has $0$ children, $p(T)$ is $[r]$.
  • If $r$ has $2$ children, let $X$ be the subtree rooted at the left child of $r$ and $Y$ the subtree rooted at the right child of $r$. Then $p(T)$ is $p(X)$, $[r]$, and $p(Y)$ concatenated in that order.
• Let $k$ be the number of leaf nodes of $T$. Number the leaves $1, 2, \cdots, k$ in the order they appear in $p(T)$, that is, in inorder visiting order.
• Selecting a subtree of $T$ covers the leaf nodes contained in it.
• For $1 ≤ a ≤ b ≤ k$, $f(a, b)$ is the minimum number of subtrees that must be selected in $T$ so that exactly the leaves numbered $a$ through $b$ are covered and no other leaf is covered.
• $S(T)$ is the sum of $f(a, b)$ over all integer pairs $(a, b)$ with $1 ≤ a ≤ b ≤ k$, taken modulo $10^9+7$.

The tree in (a) is the tree built from the definition. (b) shows the same tree with its leaves numbered.

$f(5, 7)$ is $2$. Selecting the two subtrees shown below covers only leaves $5$, $6$, and $7$.

Summing $f(a, b)$ over all $1 ≤ a ≤ b ≤ 7$ gives $47$. Taking that modulo $10^9 + 7$ gives $S(T) = 47$.

Integer sequences $A_1, A_2, \cdots, A_N$ and $B_1, B_2, \cdots, B_N$ are given.

Define binary trees $T_0, T_1, \cdots, T_N$ as follows.

• $T_0$ is a tree with one node.
• For $1 ≤ i ≤ N$, $T_i$ is the tree whose left child of the root roots the subtree $T_{A_i}$ and whose right child of the root roots the subtree $T_{B_i}$ ($0 ≤ A_i ≤ i - 1$, $0 ≤ B_i ≤ i - 1$).

Write a program that computes $S(T_1), S(T_2), \cdots, S(T_N)$.

The first line contains the integer $N$. Each of the next $N$ lines contains $A_i$ and $B_i$, separated by a space, for $i$ from $1$ to $N$.

Print $N$ lines. On line $i$ ($1 ≤ i ≤ N$), print $S(T_i)$.

• All given numbers are integers.
• $1 ≤ N ≤ 100\,000$
• $0 ≤ A_i ≤ i - 1$ ($1 ≤ i ≤ N$)
• $0 ≤ B_i ≤ i - 1$ ($1 ≤ i ≤ N$)