N = input()
M = input()
mod = 129402307

n = 0
for i in N:
    n *= 10
    n += int(i)
    n %= mod

m = 0
for i in M:
    m *= 10
    m += int(i)
    m %= (mod-1)


if n == 0 : print(0)
else : print(pow(n, m, mod))