mod = 129402307


def calc_mod(n, mod):
    res = 0
    for s in n:
        res *= 10
        res += int(s)
        res %= mod
    return res


N = input()
M = input()
if M == "0":
    print(1)
    exit()

N = calc_mod(N, mod)
M = calc_mod(M, mod - 1)
if N == 0:
    print(0)
else:
    print(pow(N, M, mod))