Enunț

Moca dorește să posteze pe Pbinfo a probleme de dificultate b. Durata postării celor a probleme de dificultate b este restul împărțirii lui $a ^ b$ la 1999999973.

Cerinta

Ajutați-l pe Moca să calculeze durata postării celor a probleme de dificultate b .

Date de intrare

Fișierul de intrare moka.in conține pe prima linie numerele a b, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire moka.out va conține pe prima linie numărul S, reprezentând restul împărțirii lui $a ^ b$

Exemplu

moka.in

2 4

moka.out

16

#include <bits/stdc++.h>
using namespace std;
ifstream cin("moka.in");
ofstream cout("moka.out");
long long putere(long long a , long long p , int mod)
{
    if(p==0) return 1;
    else
    {
       long long x = putere(a , p/2 , mod);
       if(p%2==0) return x*x%mod;
       else return x*x%mod*a%mod;
    }
}
int main()
{
    long long a , b;
    cin >> a >> b;
    cout << putere(a , b , 1999999973);
}