Se citesc doua numere naturale n si p (p prim sau nu, folosit doar ca modul). Determinati F(n) modulo p, unde F(1)=1, F(2)=1, F(k)=F(k-1)+F(k-2). Deoarece n poate fi foarte mare (F(n) ar avea milioane de cifre), folositi exponentiere matriciala pentru a calcula raspunsul in timp logaritmic.
- Date de intrare
- Se citesc n si p.
- Date de iesire
- Se afiseaza F(n) modulo p.
- Restrictii
- 1 <= n <= 10^18, 2 <= p <= 10^9
Exemple
Exemplul 1
Intrare
10 1000000007
Iesire
55
Exemplul 2
Intrare
1 1000000007
Iesire
1