Bessie's Test Case Challenge

Bessie is preparing test cases for the US Computing Olympiad in February. In each minute, she may either do nothing (spending 0 energy) or, for some positive integer \(a\), spend \(3^{a-1}\) energy to prepare \(a\) test cases.

Farmer John has \(D\) requirements. For the \(i\)th requirement, he tells Bessie that within the first \(m_i\) minutes she must have prepared at least \(b_i\) test cases. Define \(e_i\) as the minimum energy Bessie needs to satisfy the first \(i\) requirements. Your task is to compute \(e_1, e_2, \ldots, e_D\) modulo \(10^9+7\).

Note: In each minute, she can choose one of the following actions:

• Do nothing and spend 0 energy.
• For some positive integer \(a\), spend \(3^{a-1}\) energy to produce \(a\) test cases.

Hint: When \(b_i\) does not exceed \(m_i\), Bessie can simply produce 1 test case per minute. Otherwise, she may upgrade some minutes to produce extra test cases at additional energy cost. An optimal strategy is to first use each minute to produce 1 test case (costing 1 unit each), and then perform upgrades. Upgrading a minute from producing \(a\) to \(a+1\) test cases costs an extra \(2\cdot3^{a-1}\) energy. A greedy strategy that balances the upgrades among the available \(m_i\) minutes is optimal.

inputFormat

The first line contains an integer \(D\) (the number of requirements). Each of the next \(D\) lines contains two integers \(m_i\) and \(b_i\) where:

• \(1 \le m_i \le 10^6\) — the number of minutes available for the \(i\)th requirement.
• \(1 \le b_i \le 10^{12}\) — the minimum number of test cases required in the first \(m_i\) minutes.

outputFormat

Output a single line containing \(D\) space-separated integers: \(e_1, e_2, \ldots, e_D\), where \(e_i\) is the minimum energy required to satisfy the first \(i\) requirements, taken modulo \(10^9+7\).

sample

1
5 5

5