import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines 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)