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