Se citesc trei numere naturale a, n si p. Determinati a^n modulo p, folosind exponentiere rapida (bazata pe reprezentarea binara a exponentului n), in loc de a inmulti a cu el insusi de n ori.
- 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