Lemon Tree

레몬 트리는, 정점의 개수가 무한히 많은 완전 이진 트리이다. $1$번 노드는 루트이며, 번호가 $p$인 모든 정점의 자식 정점 번호는 $2p$와 $2p+1$이다. 이 트리의 정점들을 원소로 갖는 집합 $S$가 있다. 초기에 집합 $S$는 완전히 비어 있다. 다음과 같은 $Q$개의 쿼리가 입력된다.

• $p \ d$ : 정점 $p$의 자손 노드들 중, $p$와의 거리가 $d$ 이하인 정점들을 모두 $S$에 추가한다. 이때, 각각의 쿼리로부터 추가되는 정점들의 집합은 겹치지 않는다. 매 쿼리 이후에는 ${\displaystyle \sum _{i,j\in S,i}}$를 로 나눈 나머지를 출력해야 한다. 트리에서의 두 정점 , 에 대해 는 정점 와 의 거리를 의미한다.

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

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

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

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