N = int(input())
M = int(input())
MOD = 129402307

print(pow(N % MOD, M % (MOD - 1), MOD))