def str_to_modint(S: str, M: int) -> int:
    res = 0
    for a in S:
        res = (10 * res + int(a)) % M
    return res

def solve():
    Mod = 129402307
    N_str = input()
    M_str = input()

    N_mod = str_to_modint(N_str, Mod)
    M_mod = str_to_modint(M_str, Mod - 1)

    if N_mod == 0:
        if N_str == "0":
            return 0
        return 1 if M_str == "0" else 0

    return pow(N_mod, M_mod, Mod)

#==================================================
print(solve())