Bessie 正在忙于为 USA Cowmputing Olympiad 二月竞赛准备测试数据。每一分钟，她可以选择不准备任何测试数据，此时不消耗能量；或者消耗 $3^{a-1}$ 的能量来准备 $a$ 个测试数据，其中 $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 \leq b_i \leq 10^{12}$)。
令 $e_i$ 为 Bessie 满足前 $i$ 个需求所需消耗的最小能量。请输出 $e_1, \dots, e_D$ 对 $10^9+7$ 取模的结果。
输入格式
第一行包含 $D$。接下来的 $D$ 行中，第 $i$ 行包含两个空格分隔的整数 $m_i$ 和 $b_i$。
输出格式
输出 $D$ 行，第 $i$ 行包含 $e_i \pmod{10^9+7}$。
样例
样例输入 1
4 5 11 6 10 10 15 10 30
样例输出 1
21 21 25 90
说明 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$ 个需求。
样例输入 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
子任务
- 输入 4-5：$D\le 100$ 且对于所有 $i$，$m_i \le 100$。
- 输入 6-8：$D\le 3000$。
- 输入 9-20：无额外限制。