#include<cstdio>
#define MOD 1999999973
long long int n,p;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("lgput.in","r",stdin);
	freopen("lgput.out","w",stdout);
	scanf("%lld%lld",&n,&p);
}
void solve()
{
	long long int cif = 1;
	long long int a;
	if(p==0) { printf("1\n"); return; }

	a = n;
    for (int i = 0; (1<<i ) <= p; i++)  // Luam toti biti lui p la rand
    {
        if ( ((1<<i) & p) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
            cif= (cif * a) % MOD;

           a=(a * a) % MOD; // Inmultim a cu a ca sa obtinem n^(2^(i+1))
   }
	printf("%lld\n",cif);
}