N = int(input())
M = int(input())
MOD = 129402307
n = N % MOD
m = M % (MOD - 1)
if n == 0 and m == 0 and M != 0:
    print(0)
else:
    print(pow(n, m, MOD))