from math import log
N = int(raw_input())
M = int(raw_input())
p = 129402307
N %= p
ans = 1
for i in xrange(int(log(M,2))+1):
	if (M>>i)&1:
		ans = ans * N % p
	N = N**2 % p
print ans