N = int(raw_input())
M = int(raw_input())
P = 129402307

if N % P == 0 and M != 0:
    print 0
else:
    print pow(N, M % (P - 1), P)