#include <cstdio>

#define MAGIC 1999999973

long n, p;

int ntothe(long a, long b)
{
	long t1;

	switch(b)
	{
		case 1:
			return a;
		case 0:
			return 1;
	}
	
	if(b % 2)
	{
		t1 = ntothe(a, b/2);
		return (((t1*t1)%MAGIC)*a)%MAGIC;
	}
	else
	{
		t1 = ntothe(a, b/2);
		return (t1*t1)%MAGIC;
	}
}

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

	scanf("%ld%ld", &n, &p);
	
	printf("%ld\n", ntothe(n, p));

	return 0;
}