Геометрическая прогрессия
(Время: 1 сек. Память: 16 Мб Сложность: 52%)
Для заданных целых чисел a и n рассмотрим сумму следующего ряда:

Эта сумма может быть очень большой. Например, при a = 10 и n = 999999 значение суммы состоит из миллиона цифр!
Требуется найти остаток от деления этой суммы на натуральное число m.
Входные данные
В единственной строке входного файла INPUT.TXT даны три целых числа a, n и m (1 ≤ |a| ≤ 1018, 0 ≤ n ≤ 1018, 1 ≤ m ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное неотрицательное целое число – ответ на задачу.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | -4 10 2 | 1 |
2 | 2 31 10 | 5 |
3 | 10 9999 9 | 1 |
Система оценки
Решения, работающие для a, n и m, не превосходящих 10 по абсолютной величине, будут оцениваться в 20 баллов.
Решения, работающие для n ≤ 106, будут оцениваться в 40 баллов.
Решения, работающие для взаимнопростых значений m и a-1, будут оцениваться в 80 баллов.
Автор задачи
Дмитрий Козырев
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|