N = input()
M = input()
p = 129402307
n, m = 0, 0
for s in N:
    n *= 10
    n += int(s)
    n %= p
for s in M:
    m *= 10
    m += int(s)
    m %= (p - 1)
if M == "0":
    print(1)
elif n == 0:
    print(0)
else:
    print(pow(n, m, p))