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