Fibonacci ədədlərinin ümumiləşdirilməsi

Ümumi Fibonacçi ədədləri F_n^(k) aşağıdakı ardıcıllıqla təyin olunur:

Sizin vəzifəniz F_n^(k) ədədinin p ilə bölünməsindən alınan qalığı tapmaqdır.

Giriş verilənləri

Giriş faylı üç tam ədəd ehtiva edir: n, k və p (1 ≤ n, k ≤ 10^6, 2 ≤ p ≤ 10^9).

Çıxış verilənləri

Çıxış faylına F_n^(k) mod p ədədini yazın.

Nümunələr