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 3a−1 energy preparing a test cases, for some positive integer a.
Farmer John has D (1≤D≤2⋅105) demands. For the ith demand, he tells Bessie that within the first mi minutes, she needs to have prepared at least bi test cases in total (1≤mi≤106,1≤bi≤1012).
Let ei be the smallest amount of energy Bessie needs to spend to satisfy the first i
demands. Print e1,…,eD modulo 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains D. The ith of the next D lines contains two space-separated integers mi and bi .
OUTPUT FORMAT (print output to the terminal / stdout):
Output D lines, the ith containing ei mod 109+7.
SAMPLE INPUT:
4
5 11
6 10
10 15
10 30
SAMPLE OUTPUT:
21
21
25
90
For the first test case,
i=1: If Bessie creates [2,3,2,2,2] test cases on the first 5 days, respectively, she would have expended 31+32+31+31+31=21 units of energy and created 11
test cases by the end of day 5.
i=2: Bessie can follow the above strategy to ensure 11 test cases are created by the end of day 5, and this will automatically satisfy the second demand.
i=3: If Bessie creates [2,3,2,2,2,0,1,1,1,1] test cases on the first 10 days, respectively, she would have expended 25 units of energy and satisfied all demands. It can be shown that she cannot expend less energy.
i=4: If Bessie creates 3 test cases on each of the first 10 days she would have expended 32⋅10=90 units of energy and satisfied all demands.
For each i, it can be shown that Bessie cannot satisfy the first i demands using less energy.
SAMPLE INPUT:
2
100 5
100 1000000000000
SAMPLE OUTPUT:
5
627323485
SAMPLE INPUT:
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
SAMPLE OUTPUT:
108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759
SCORING:
Inputs 4-5: D≤100 and mi≤100 for all i
Inputs 6-8: D≤3000
Inputs 9-20: No additional constraints.
Problem credits: Brandon Wang and Claire Zhang
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
