Пенсионный фонд
(Время: 2 сек. Память: 32 Мб Сложность: 90%)
Алексей несколько лет назад решил заранее начать откладывать деньги на пенсию. Для этого он открыл счета в T пенсионных фондах и стал делать в каждый из них один взнос в конце каждого месяца.
Когда Алексей только начинал карьеру, его доход был небольшим, но он рассчитывал, что с опытом будет зарабатывать всё больше. Поэтому он заранее выбрал простое правило для ежемесячных взносов: Kp рублей (в первый месяц 1p рублей, во второй месяц – 2p рублей, в третий месяц – 3p рублей, и так далее).
Каждый пенсионный фонд ежемесячно увеличивает всю накопленную сумму в M раз. Это происходит один раз в конце каждого месяца после внесения очередного взноса.
Алексей делал взносы таким образом в течение N месяцев и теперь хочет узнать, сколько стоят все его накопления после окончания N-го месяца в каждом пенсионном фонде. Так как ответ может быть очень большим, выведите его по модулю 109+7.
Входные данные
Входной файл INPUT.TXT в первой строке содержит натуральное число T. Далее в каждой строке по три натуральных числа: N, M, P (1 ≤ N, M ≤ 1018; 1 ≤ T ≤ 10; 1 ≤ P ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ для каждого пенсионного фонда с новой строки.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 2 3
2 3 4
3 2 1 | 2
147
34 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
