Se citesc trei numere naturale a, n si p. Determinati a^n modulo p, implementand exponentierea rapida recursiv: a^n = (a^(n/2))^2 daca n este par, respectiv a * a^(n-1) daca n este impar, cu cazul de baza a^0 = 1.
- Date de intrare
- Se citesc a, n si p.
- Date de iesire
- Se afiseaza a^n modulo p.
- Restrictii
- 0 <= a < 10^9, 0 <= n <= 10^18, 2 <= p <= 10^9
Exemple
Exemplul 1
Intrare
2 10 1000
Iesire
24
Exemplul 2
Intrare
3 5 100
Iesire
43