The Lemon Tree is a complete binary tree with an infinite number of vertices. Node $1$ is the root, and the child vertices of any vertex numbered $p$ are numbered $2p$ and $2p+1$. There is a set $S$ whose elements are vertices of this tree. Initially, the set $S$ is empty. $Q$ queries are given as follows.

• $p \ d$ : Among the descendants of vertex $p$, including $p$, add all vertices whose distance to $p$ is less than or equal to $d$ into $S$. Here, it is guaranteed that the sets of vertices added by each query do not overlap.

After each query, you must output the remainder of $\displaystyle \sum_{i, j \in S, \ i<j} \mathrm{dist}(i, j)$ divided by $10^9+7$. For two vertices $i$ and $j$ in the tree, $\mathrm{dist}(i, j)$ means the distance between vertex $i$ and $j$.

$Q$ is given on the first line. From the second line, the queries $p$ and $d$ are given separated by a space, one per line over $Q$ lines.

Print $\displaystyle \sum_{i, j \in S, \ i<j} \mathrm{dist}(i, j) \bmod{10^9+7}$ immediately after each query, one per line.

• $1 \le Q \le 100 \ 000$
• $1 \le p < 2^{50}$, $0 \le d < 50$, $1 \le p \times 2^d < 2^{50}$