Se citesc doua numere naturale n si p. Determinati L(n) modulo p, unde L(0)=2, L(1)=1, L(k)=L(k-1)+L(k-2) (sirul lui Lucas). Deoarece n poate fi foarte mare, folositi exponentiere matriciala.
- Date de intrare
- Se citesc n si p.
- Date de iesire
- Se afiseaza L(n) modulo p.
- Restrictii
- 0 <= n <= 10^18, 2 <= p <= 10^9
Exemple
Exemplul 1
Intrare
0 1000000007
Iesire
2
Exemplul 2
Intrare
1 1000000007
Iesire
1