MOD = 129402307 n = list(map(int, list(input()))) m = list(map(int, list(input()))) s = len(n) t = len(m) x = 0 for i in range(s): x = (x * 10 + n[i]) % MOD y = 0 for i in range(t): y = (y * 10 + m[i]) % (MOD - 1) if x == 0: print("0") elif y == 0: print("1") else: print(pow(x, y, MOD))