| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 35 | 15 | 15 | 48.387% |
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$.
4 5 11 6 10 10 15 10 30
21 21 25 90
For the first test case,
For each $i,ドル it can be shown that Bessie cannot satisfy the first $i$ demands using less energy.
2 100 5 100 1000000000000
5 627323485
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
108753959 108753959 108753959 148189797 148189797 148189797 148189797 32884410 32884410 32884410 32884410 32884410 32884410 32884410 3883759 3883759 3883759 3883759 3883759 3883759