题目描述

题目来自 USACO 2024 February Contest, Platinum Problem 1. Lazy Cow

Bessie 正在努力为美国计算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 \(a\)，花费 \(3^{a-1}\) 能量准备 \(a\) 个测试用例。

Farmer John 有 \(D\)（\(1 \le D \le 2 \times 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

输入

(4) (5) (11) (6) (10) (10) (15) (10) (30)

输出

(21) (21) (25) (90)

说明

对于第一个测试用例：

• (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)

输出

(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)

输出

(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：没有额外限制。