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

import sys

N %= P
M %= (P-1)
if N == 0:
    print(0)
    exit()
print(pow(N,M,P))