#include <iostream>
#include <cstdio>

using namespace std;

const int modulo = 1999999973;

int main()
{
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);

    int p,i;
    unsigned long long sol=1, n;

    cin>>n>>p;

    for (i=0; (1<<i) <= p; ++i){
        if ( ( (1<<i)&p ) > 0)
            sol = (sol * n) % modulo;
        n = (n * n) % modulo;
    }
    cout<<sol<<'\n';
    return 0;
}