Узагальнені числа Фібоначчі#4806
Узагальненими числами Фібоначчі F_n^{(k)} називають наступну послідовність:
Ваша задача - обчислити залишок від ділення F_n^{(k)} на .
Вхідний файл містить три цілих числа: , та (1 \leq n, k \leq 10^6, 2 \leq p \leq 10^9).
У вихідний файл виведіть F_n^{(k)} \bmod p.
Приклад 1