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}3^\{a-1\}$ energy preparing $aa$ test cases, for some positive integer $aa$.

Farmer John has $DD$ ($1\le D\le 2\cdot {10}^{5}1\backslash le\; D\backslash le\; 2\backslash cdot\; 10^5$) demands. For the $ii$th demand, he tells Bessie that within the first $m_{i}m\_i$ minutes, she needs to have prepared at least $b_{i}b\_i$ test cases in total ($1\le m_i\le {10}^6,1\le b_i\le {10}^{12}1\backslash le\; m\_i\backslash le\; 10^6,\; 1\; \backslash leq\; b\_i\; \backslash leq\; 10^\{12\}$).

Let $e_{i}e\_i$ be the smallest amount of energy Bessie needs to spend to satisfy the first $ii$ demands. Print $e_1,\dots ,e_{D}e\_1,\backslash dots,e\_D$ modulo ${10}^9+710^9+7$.

입력

The first line contains $DD$. The $ii$th of the next $DD$ lines contains two space-separated integers $m_{i}m\_i$ and $b_{i}b\_i$.

출력

Output $DD$ lines, the $ii$th containing $e_i\text{ mod }{10}^9+7e\_i\; \backslash text\{\; mod\; \}\; 10^9+7$.