Обобщённые числа Фибоначчи

Очень простая

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 64 мегабайта

Обобщёнными числами Фибоначчи F_n^{(k)} называют следующую последовательность:

Ваша задача - вычислить остаток от деления F_n^{(k)} на p.

Входные данные

Входной файл содержит три целых числа: n, k и p (1 ≤ n, k ≤ 10^6, 2 ≤ p ≤ 10^9).

В выходной файл выведите F_n^{(k)} mod p.

Ввод #1

Ответ #1

Отправки 139

Коэффициент принятия 33 %