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

Output $D$ lines, the $i$th containing $e_i \text{ mod } 10^9+7$.