#include <stdio.h>

long a, b, c=1999999973, rez;

int main()
{
	long p=1, pp, v, vv;
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);
	scanf("%ld %ld", &a, &b);
        v=a;
	a%=c;
	b%=(c-1);
	while (p<b)
	{
		pp=1;
		vv=a;
		while (p+pp<=b)
		{
			p+=pp;
			pp+=pp;
			v*=vv;
			v%=c;
			vv*=vv;
			vv%=c;
		}
	}
        v%=c;
        printf("%ld\n", v);
	return 0;
}