import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines

n=int(readline())
m=int(readline())
if n==0:
    print(0)
    exit()
MOD=129402307
n%=MOD
if n==0:
    if m==0:
        print(1)
    else:
        print(0)
    exit()
print(pow(n, m%(MOD-1), MOD))