题目描述

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

4
5 11
6 10
10 15
10 30

21
21
25
90

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

提示

样例解释 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$：没有额外限制。