# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import *
from itertools import *
from functools import *
from heapq import *
import sys,math
input = sys.stdin.readline

N = int(input())
M = int(input())
mod = 129402307
if N%mod==0:
    print(0)
    exit()
M = M%(mod-1)
print(pow(N,M,mod))