#include <fstream>
#define N 1999999973
using namespace std;

int main()
{
    ifstream f("lgput.in");
    ofstream g("lgput.out");
    long long n, put, init[100000], k=0;
    bool par=0;
    f>>n>>put;
    while(put>1)
    {
        if(put%2==0)
            n=n*n, put/=2;
        else
            init[k++]=n, n=n*n, put-=1, put/=2, par=1;
    }
    if(par==1)
        for(int i=0; i<k; i++)
            n*=init[i];
    if(n!=0)
        g<<N%n;
    return 0;
}