MOD = 129402307

S = input()
n = 0
for s in S:
    n *= 10
    n += int(s)
    n %= MOD

S = input()
m = 0
for s in S:
    m *= 10
    m += int(s)
    m %= (MOD - 1)
if n == 0:
    print(0)
else:
    print(pow(n, m, MOD))