#include<cstdio>
#define MOD 1999999973
using namespace std;

long long putere(long long, long long);

int main()
{
	long long n, p;
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);
	scanf("%lld %lld", &n, &p);
	printf("%lld", putere(n, p));
	return 0;
}

long long putere(long long n, long long p)
{
	if(p == 1)
		return n;
	long long x = putere(n, p/2);
	if(p % 2)
	{
		return (x * x * n) % MOD;
	}
	else
	{
		return (x * x) % MOD;
	}
}