Узагальнені числа Фібоначчі

Узагальненими числами Фібоначчі F_n^{(k)} називають наступну послідовність:

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

Вхідні дані

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

Вихідні дані

У вихідний файл виведіть F_n^{(k)} mod p.

Приклади