¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8151
Subtarea

Lazy Cow 2s 1024MB

Problemas

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.


Entrada

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


Salida

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


Subtarea

# Puntaje Condición
#120

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

#230

D \le 3,000

#350

추가 제약 조건 없음


Ejemplo #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.


Ejemplo #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

Fuente

USACO 2024 February Platinum 1번

Debes iniciar sesión para escribir código.