N = list(input())
M = list(input())
mod = 129402307
n, m = 0, 0
ten = 1
for a in reversed(N):
    n += ten * int(a)
    ten *= 10
    n %= mod
    ten %= mod

ten = 1
for a in reversed(M):
    m += ten * int(a)
    ten *= 10
    m %= mod - 1
    ten %= mod - 1

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