#include <bits/stdc++.h>

using namespace std;

ifstream in("lgput.in");
ofstream out("lgput.out");

int main()
{
    unsigned long long A,B,ans;
    unsigned long long C;
    int bit;
    in>>A;
    in>>B;
    in>>C;
    ans=1;
    C=1999999973;
    for(bit=0;(1<<bit)<=B;++bit)
    {
        if(B&(1<<bit))
            ans=ans*A%C;
        A=A*A%C;
    }
    out<<ans;
    return 0;
}