当前没有测试数据。

一、题目名称

懒牛（Lazy Cow）

二、题目描述

贝西（Bessie）正在努力为美国计算机奥林匹克竞赛（USA Cowmputing Olympiad）二月赛准备测试用例。每分钟，她可以选择不准备任何测试，不消耗能量；或者消耗$3^{a - 1}$能量来准备$a$个测试用例，其中$a$为某个正整数。

农夫约翰（Farmer John）有$D$（$1\leq D\leq2\cdot10^5$）个需求。对于第$i$个需求，他告诉贝西在最初的$m_i$分钟内，她总共需要准备至少$b_i$个测试用例（$1\leq m_i\leq10^6$，$1\leq b_i\leq10^{12}$）。

设$e_i$为贝西满足前$i$个需求所需消耗的最小能量。输出$e_1,\cdots,e_D$对$10^9 + 7$取模的结果。

三、输入格式（从终端/标准输入读取）

1. 第一行包含$D$。接下来的$D$行，第$i$行包含两个用空格分隔的整数$m_i$和$b_i$。

四、输出格式（打印输出到终端/标准输出）

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

五、样例输入及输出

样例输入1

4
5 11
6 10
10 15
10 30

样例输出1

21
21
25
90

解释：对于第一个测试用例，当$i = 1$时：如果贝西在前$5$天分别准备$[2,3,2,2,2]$个测试用例，那么她将消耗$3^1 + 3^2 + 3^1 + 3^1 + 3^1 = 21$单位能量，并在第$5$天结束时准备了$11$个测试用例。当$i = 2$时：贝西可以采用上述策略确保在第$5$天结束时准备了$11$个测试用例，这将自动满足第二个需求。当$i = 3$时：如果贝西在前$10$天分别准备$[2,3,2,2,2,0,1,1,1,1]$个测试用例，她将消耗$25$单位能量并满足所有需求。可以证明她不能消耗更少的能量。当$i = 4$时：如果贝西在前$10$天每天准备$3$个测试用例，她将消耗$3^2\cdot10 = 90$单位能量并满足所有需求。对于每个$i$，可以证明贝西不能使用更少的能量来满足前$i$个需求。

样例输入2

2
100 5
100 1000000000000

样例输出2

5
627323485

样例输入3

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

样例输出3

108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759

六、评分规则

1. 输入4 - 5：$D\leq100$且对于所有$i$，$m_i\leq100$。
2. 输入6 - 8：$D\leq3000$。
3. 输入9 - 20：无其他额外约束。

题目来源：Brandon Wang和Claire Zhang。