Problem Description

Bessie is diligently preparing test cases for the February competition of the USACO. Each minute, she can choose not to prepare any test cases, thus expending no energy, or for some positive integer \( a \), she can expend \( 3^{a-1} \) units of energy to prepare \( a \) test cases.

Farmer John has \( D \) (\( 1 \le D \le 2 \cdot 10^5 \)) requirements. For the \( i \)-th requirement, he informs Bessie that she needs to prepare at least \( b_i \) test cases within the first \( m_i \) minutes (\( 1 \le m_i \le 10^6, 1 \le b_i \le 10^{12} \)).

Let \( e_i \) be the minimum energy Bessie needs to expend to meet the first \( i \) requirements. Output \( e_1, \ldots, e_D \) modulo \( 10^9+7 \).

Input Format

The first line of input contains \( D \). The following \( D \) lines each contain two space-separated integers \( m_i \) and \( b_i \).

Output Format

Output \( D \) lines, the \( i \)-th line containing \( e_i \bmod 10^9+7 \).

Sample Input and Output

Input Sample #1

4
5 11
6 10
10 15
10 30

Output Sample #1

21
21
25
90

Input Sample #2

2
100 5
100 1000000000000

Output Sample #2

5
627323485

Input Sample #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

Output Sample #3

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

Notes/Hints

Sample Explanation 1

For the first test case,

• \( i=1 \): If Bessie prepares \( [2, 3, 2, 2, 2] \) test cases over the first 5 days, she will expend \( 3^1 + 3^2 + 3^1 + 3^1 + 3^1 = 21 \) units of energy and will have prepared 11 test cases by the end of the 5th day.
• \( i=2 \): Bessie can follow the above strategy to ensure she has prepared 11 test cases by the end of the 5th day, which will automatically satisfy the second requirement.
• \( i=3 \): If Bessie prepares \( [2, 3, 2, 2, 2, 0, 1, 1, 1, 1] \) test cases over the first 10 days, she will expend 25 units of energy and meet all requirements. It can be proven that she cannot expend less energy.
• \( i=4 \): If Bessie prepares 3 test cases each day for the first 10 days, she will expend \( 3^2 \cdot 10 = 90 \) units of energy and meet all requirements.

For each \( i \), it can be proven that Bessie cannot expend less energy to meet the first \( i \) requirements.

Test Case Properties

• Test points \( 4-5 \): \( D \le 100 \) and for all \( i \), \( m_i \le 100 \).
• Test points \( 6-8 \): \( D \le 3000 \).
• Test points \( 9-20 \): No additional restrictions.

见题面 Input 部分

见题面 Output 部分