n = gets.to_i
m = gets.to_i
md = 129_402_307
sn = n % md
k = 1
mmd = 100
while true do
    q = m % mmd
    k = (k * ((sn ** q) % md)) % md
    break if m < mmd
    sn = (sn ** mmd) % md
    m /= mmd
end
puts k