#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    unsigned long long a, b, c=1999999973, ans=1;
    // a=b; b=e; c=mod;
    in>>a>>b>>c;
    for (int bit=0; (1<<bit)<=b; ++bit)
    {
        if (b & (1<<bit))
            ans=ans*a%c;
        a=a*a%c;
    }
    out<<ans;
    return 0;
}