Беси готовит тесты для олимпиады. Каждую минуту она может выбрать не готовить
никакие тесты для экономии энергии или потратить \(3^{a-1}\) энергии для подготовки
\(a\) тестов для некоторого положительного целого \(a\).
У Фермера Джона есть \(D\) (\(1\le D\le 2\cdot 10^5\)) требований. Для \(i\)-го
требования он говорит Беси, что в течение первых \(m_i\) минут она должна приготовить
не менее чем \(b_i\) тестов (\(1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}\)).
Пусть \(e_i\) - минимальное количество энергии, которое необходимо Беси, чтобы
удовлетворить первые \(i\) требований. Выведите \(e_1,\dots,e_D\) по модулю \(10^9+7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит \(D\). \(i\)-ая из следующих \(D\) строк содержит два
разделённых одиночным пробелом целых числа \(m_i\) и \(b_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(D\) строк, где \(i\)-ая строка содержит \(e_i \text{ mod } 10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 11
6 10
10 15
10 30
|
21
21
25
90
|