페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8151
서브태스크

Lazy Cow 2s 1024MB

문제

Bessie is hard at work preparing test cases for the USA Cowmputing Olympiad February contest. Each minute, she can choose to not prepare any tests, expending no energy; or expend 3^{a-1} energy preparing a test cases, for some positive integer a.

Farmer John has D (1\le D\le 2\cdot 10^5) demands. For the ith demand, he tells Bessie that within the first m_i minutes, she needs to have prepared at least b_i test cases in total (1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}).

Let e_i be the smallest amount of energy Bessie needs to spend to satisfy the first i demands. Print e_1,\dots,e_D modulo 10^9+7.


입력

The first line contains D. The ith of the next D lines contains two space-separated integers m_i and b_i.


출력

Output D lines, the ith containing e_i \text{ mod } 10^9+7.


부분문제

번호 점수 조건
#120점

D \le 100; m_i \le 100 (1 \le i \le D)

#230점

D \le 3,000

#350점

추가 제약 조건 없음


예제 #1

4
5 11
6 10
10 15
10 30
21
21
25
90

For the first test case,

  • i=1: If Bessie creates [2, 3, 2, 2, 2] test cases on the first 5 days, respectively, she would have expended 3^1 + 3^2 + 3^1 + 3^1 + 3^1 = 21 units of energy and created 11 test cases by the end of day 5.

  • i=2: Bessie can follow the above strategy to ensure 11 test cases are created by the end of day 5, and this will automatically satisfy the second demand.

  • i=3: If Bessie creates [2, 3, 2, 2, 2, 0, 1, 1, 1, 1] test cases on the first 10 days, respectively, she would have expended 25 units of energy and satisfied all demands. It can be shown that she cannot expend less energy.

  • i=4: If Bessie creates 3 test cases on each of the first 10 days she would have expended units of energy and satisfied all demands.

For each i, it can be shown that Bessie cannot satisfy the first i demands using less energy.


예제 #2

2
100 5
100 1000000000000
108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759

출처

USACO 2024 February Platinum 1번

로그인해야 코드를 작성할 수 있어요.