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

import sys


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