/*
Ridicarea la putere cu complexitatea logaritmica. Sa se calc (a^b) % m unde 2 < a,b < 1.000.000.000 si se dau a, b, m.
O(log2 b)
*/

/*
2^100 = 2^4 * 2^32 * 2^64

2^1, 2^2, 2^4, 2^8, 2^16, ...

100 = 1*64 + 1*32 + 0 *16 + 0*8 + 1*4 + 0*2 + 0*1
(1100100)

b = 100
----------
a^1 	0
a^2 	0
a^4		1
a^8 	0
a^16	0
a^32	1
a^64	1

b = 452
----------
a^1 	0
a^2 	0
a^4		1
a^8 	0
a^16	0
a^32	0
a^64	1
a^128	1
a^256	1



*/


#include <stdio.h>

FILE *in, *out;
long long a, b, m, p;

int main () {
	long long x;
	int r, y;

	in 	= fopen("lgput.in", "r");
	out = fopen("lgput.out", "w");

	fscanf(in, "%lld", &a);
	fscanf(in, "%lld", &b);

	m = 1999999973;

	p = 1;
	x = a;
	y = b;

	while (y != 0)
	{
		r = y % 2;
		// printf("%d %d \n", x, r);

		if (r==1)
		{
			p = (p * x) % m;
		}
		
		x = (x * x) % m;
		y = y / 2;
	}

	fprintf(out, "%lld \n", p);

	fclose(out);
	fclose(in);

	return 0;
}