#include<stdio.h>
#define mod 1999999973
using namespace std;

int n,p;
long long sol,add;

void read()
{
    scanf("%d%d",&n,&p);
}

void solve()
{
    sol=1; add=n;
    for(int i=0;(p>>i)>0;i++)
    {
        if( ((p>>i)&1)==1 ) sol=(sol*add)%mod;
        add=(add*add)%mod;
    }
    printf("%lld",sol);
}

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

    read();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}