Lemon Tree

레몬 트리는, 정점의 개수가 무한히 많은 완전 이진 트리이다. $1$번 노드는 루트이며, 번호가 $p$인 모든 정점의 자식 정점 번호는 $2p$와 $2p+1$이다.

이 트리의 정점들을 원소로 갖는 집합 $S$가 있다. 초기에 집합 $S$는 완전히 비어 있다. 다음과 같은 $Q$개의 쿼리가 입력된다.

$p \ d$ : 정점 $p$의 자손 노드들 중, $p$와의 거리가 $d$ 이하인 정점들을 모두 $S$에 추가한다. 이때, 각각의 쿼리로부터 추가되는 정점들의 집합은 겹치지 않는다.

매 쿼리 이후에는 $\displaystyle \sum_{i, j \in S, \ i<j} \mathrm{dist}(i, j)$를 $10^9+7$로 나눈 나머지를 출력해야 한다.

트리에서의 두 정점 $i$, $j$에 대해 $\mathrm{dist}(i, j)$는 정점 $i$와 $j$의 거리를 의미한다.

첫째 줄에 $Q$가 주어진다.

둘째 줄부터 $Q$개의 줄에 쿼리 $p$, $d$가 한 줄에 하나씩 공백으로 구분되어 주어진다.

매 쿼리 직후의 $\displaystyle \sum_{i, j \in S, \ i<j} \mathrm{dist}(i, j) \bmod{10^9+7}$을 한 줄에 하나씩 출력한다.

첫 번째 쿼리 이후 $S=\{1, 2, 3\}$이다. 따라서 구하고자 하는 값은 $\mathrm{dist}(1, 2)+\mathrm{dist}(1, 3)+\mathrm{dist}(2, 3)=1+1+2=4$ 이다.

두 번째 쿼리 이후 $S=\{1, 2, 3, 8\}$이다. 따라서 구하고자 하는 값은 $\mathrm{dist}(1, 2)+\mathrm{dist}(1, 3)+\mathrm{dist}(1, 8)+\mathrm{dist}(2, 3)+\mathrm{dist}(2, 8)+\mathrm{dist}(3, 8)=1+1+3+2+2+4=13$ 이다.

[제한]

$1 \le Q \le 100 \ 000$

$1 \le p < 2^{50}$, $0 \le d < 50$, $1 \le p \times 2^d < 2^{50}$

$p$는 양의 정수, $d$는 음이 아닌 정수이다.

[서브태스크]

$Q=1$ (11)

$Q=2$ (23)

$\mathrm{max}(p \times 2^d) < 2^{20}$ (29)

추가 조건 없음 (37)