def modulo(s: str, m: int) -> int:
    x = 0
    for c in map(int, s):
        x = (10*x + c) % m
    return x


MOD = 129402307
N = input()
M = input()

ans = 1
a = modulo(N, MOD)
for d in reversed([int(c) for c in M]):
    ans *= pow(a, d, MOD)
    ans %= MOD

    a = pow(a, 10, MOD)

print(ans)