MOD = 129402307
n = gets.to_i % MOD
m = gets.to_i
ans = 1
m.to_s(2).size.times{|i|
    if m[i] == 1
        ans = (ans * n) % MOD
    end
    n = (n * n) % MOD
    }
p ans