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 $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$.

• 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.

Output $D$ lines, the $i$th containing $e_i \text{ mod } 10^9+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 $3^1 + 3^2 + 3^1 + 3^1 + 3^1 = 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 $3^{2}\cdot 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.