Se considera sirul definit prin a(0)=1, a(k)=2*a(k-1) (adica a(k)=2^k). Se citesc doua numere naturale n si p. Determinati a(n) modulo p, folosind exponentiere rapida (deoarece n poate fi foarte mare, iar 2^n ar avea prea multe cifre pentru a fi calculat direct).
- Date de intrare
- Se citesc n si p.
- Date de iesire
- Se afiseaza 2^n modulo p.
- Restrictii
- 0 <= n <= 10^18, 2 <= p <= 10^9
Exemple
Exemplul 1
Intrare
0 1000000007
Iesire
1
Exemplul 2
Intrare
10 1000000007
Iesire
1024