34257번 - Lemon Tree🍋🌳 서브태스크

문제

Lemon Tree🍋🌳는 정점의 개수가 충분히 많은 완전 이진 트리 형태이다. 루트 노드는 1ドル$번 정점이며, 임의의 정점 $p$에 대해 왼쪽 위에는 2ドルp$번 정점, 오른쪽 위에는 2ドルp+1$번 정점이 길이 1ドル$의 간선으로 연결되어 있다.

Lemon Tree🍋🌳에서는 $Q$일 동안 매일 몇 개의 레몬이 열린다. 구체적으로, $i$번째 날 아침에는 정점 $P_i$에서 위쪽으로만 이동해 도달할 수 있고, $P_i$와의 거리가 $D_i$ 이하인 모든 정점에서 레몬이 하나씩 열린다. 단, 새로 레몬이 열리는 범위 내의 모든 정점에 레몬이 열렸던 적이 없음이 보장된다.

Lemon Tree🍋🌳를 가꾸던 우현이는 이런 의문이 들었다.

“나무 위에 열린 모든 두 레몬 쌍에 대해, 그 사이의 거리를 전부 합한 값은 얼마일까?”

우현이를 위해, 첫 번째 날 밤부터 $Q$번째 날 밤까지의 상황에 대한 답을 구해보자. 단, 답이 매우 클 수 있으므로 10ドル^9+7$로 나눈 나머지를 구해보자.

입력

입력은 다음과 같은 형식으로 주어진다.

$Q$

$P_1 \ D_1$

$P_2 \ D_2$

$\vdots$

$P_Q \ D_Q$

출력

첫째 줄부터 $Q$개의 줄에 걸쳐 $i$번째 날 밤 우현이의 질문에 대한 답을 한 줄에 하나씩 출력한다.

제한

• 1ドル \le Q \le 100 \ 000$.
• 1ドル \le P_i < 2^{50}$ (1ドル \le i \le Q)$.
• 0ドル \le D_i < 50$ (1ドル \le i \le Q$).
• 1ドル \le P_i \times 2^{D_i} < 2^{50}$ (1ドル \le i \le Q$).
• 새로 레몬이 열리는 범위 내의 모든 정점에 레몬이 열렸던 적이 없음이 보장된다.

입력되는 모든 값은 정수이다.

서브태스크

힌트