import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
m=int(input())
mod=129402307
if m==0:
  print(1)
else:
  n%=mod
  m%=mod-1
  if n==0:
    print(0)

  else:
    print(pow(n,m,mod))