Lazy Cow
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.
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.
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
Source: USA Computing Olympiad.
Input Format
The first line contains D. The ith of the next D lines contains two space-separated integers mi and bi.
Output Format
Output D lines, the ith containing ei mod 109+7.