n = gets.to_i
m = gets.to_i

k = (n%(m*1000))/1000

p m**k%1000000000