n = gets.to_i m = gets.to_i k = (n%(m*1000))/1000 p n**k%1000000000