import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

sys.set_int_max_str_digits(10**6)
N,M = map(int,read().split())

MOD = 129402307

N %= MOD
if M > MOD:
    M %= (MOD - 1);
    M += (MOD - 1)
answer = pow(N,M,MOD)
print(answer)