P10196 [USACO24FEB] Lazy Cow P

Bessie 正在努力为美国件算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 $a$，花费 $3^{a−1}$ 能量准备 $a$ 个测试用例。 Farmer John 有 $D$（$1\le D\le 2\cdot 10^5$）个需求。对于第 $i$ 个需求，他告诉 Bessie，在前 $m_i$ 分钟内她总共需要准备至少 $b_i$ 个测试用例（$1\le m_i\le 10^6,1\le b_i\le 10^{12}$）。 令 $e_i$ 为满足前 $i$ 个需求 Bessie 最小需要花费的能量。输出 $e_1,\ldots,e_D$ 模 $10^9+7$ 的余数。

输入的第一行包含 $D$。以下 $D$ 行，第 $i$ 行包含两个空格分隔的整数 $m_i$ 和 $b_i$。

输出 $D$ 行，第 $i$ 行包含 $e_i \bmod 10^9+7$。

### 样例解释 1 对于第一个测试用例， - $i=1$：如果 Bessie 在前 $5$ 天分别制作 $[2,3,2,2,2]$ 个测试用例，她将花费 $3^1+3^2+3^1+3^1+3^1=21$ 单位能量，并在第 $5$ 天结束时制作了 $11$ 个测试用例。 - $i=2$：Bessie 可以遵循上面的策略，确保在第 $5$ 天结束时制作了 $11$ 个测试用例，而这将自动满足第二个需求。 - $i=3$：如果 Bessie 在前 $10$ 天分别制作 $[2,3,2,2,2,0,1,1,1,1]$ 个测试用例，她将花费 $25$ 单位能量并满足所有需求。可以证明她无法花费更少的能量。 - $i=4$：如果 Bessie 在前 $10$ 天每一天制作 $3$ 个测试用例，她将花费 $3^2\cdot 10=90$ 单位能量并满足所有需求。 对于每一个 $i$，可以证明 Bessie 无法花费更少的能量满足前 $i$ 个需求。 ### 测试点性质 - 测试点 $4-5$：$D\le 100$，且对于所有 $i$，$m_i\le 100$。 - 测试点 $6-8$：$D\le 3000$。 - 测试点 $9-20$：没有额外限制。