MOD = 129402307
MOD2 = MOD-1
n = int(input())%MOD
m = int(input())
if m==0: print(1)
else:
    m = m%MOD2+MOD2
    print(pow(n,m,MOD))