#include <iostream>
#include <fstream>
using namespace std;
unsigned power(unsigned n, unsigned k)
{
    unsigned x=n;
    for(unsigned i=1;i<k;i++)
        n*=x;
    return n;
}
unsigned divide(unsigned n, unsigned x)
{
    if(x)
    {
        if(x%2==0)
            divide(power(n,2),x/2);
        else
        {
            bool felt=1;
            for(unsigned i=3;i<x/2 && felt;i+=2)
            {
                if(x%i==0)
                {
                    felt=0;
                    return divide(power(n,i),x/i);
                }
            }
            if(felt)
                return power(n,x);
        }
    }
    else
        return power(n,x);
}
unsigned long long divide_2(unsigned long long N, unsigned long long P)
{
    if(P)
    {
        long long k=divide_2(N,P/2);
        k=(k*k)%1999999973;
        if(P%2!=0)
            k=(k*N)%1999999973;
        return k%1999999973;
    }
    return 1;
}
int main()
{
    ifstream f("lgput.in");
    ofstream g("lgput.out");
    unsigned long long N, P;
    f>>N>>P;
    g<<divide_2(N,P);
    f.close();
    g.close();
    //cin>>N>>P;
    //cout<<divide_2(N,P);
    return 0;
}