문제

Bessie is hard at work preparing test cases for the USA Cowmputing Olympiad February contest. Each minute, she can choose to not prepare any tests, expending no energy; or expend $3^{a-1}$ energy preparing $a$ test cases, for some positive integer $a$.

Farmer John has $D$ ($1\le D\le 2\cdot 10^5$) demands. For the $i$th demand, he tells Bessie that within the first $m_i$ minutes, she needs to have prepared at least $b_i$ test cases in total ($1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}$).

Let $e_i$ be the smallest amount of energy Bessie needs to spend to satisfy the first $i$ demands. Print $e_1,\dots,e_D$ modulo $10^9+7$.

입력

The first line contains $D$. The $i$th of the next $D$ lines contains two space-separated integers $m_i$ and $b_i$.

출력

Output $D$ lines, the $i$th containing $e_i \text{ mod } 10^9+7$.

예제 입력 1

4
5 11
6 10
10 15
10 30

예제 출력 1

21
21
25
90

예제 입력 2

2
100 5
100 1000000000000

예제 출력 2

5
627323485

예제 입력 3

20
303590 482848034083
180190 112716918480
312298 258438719980
671877 605558355401
662137 440411075067
257593 261569032231
766172 268433874550
8114 905639446594
209577 11155741818
227183 874665904430
896141 55422874585
728247 456681845046
193800 632739601224
443005 623200306681
330325 955479269245
377303 177279745225
880246 22559233849
58084 155169139314
813702 758370488574
929760 785245728062

예제 출력 3

108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759

점수

Inputs 4-5: $D\le 100$ and $m_i \le 100$ for all $i$ Inputs 6-8: $D\le 3000$Inputs 9-20: No additional constraints.