k=gets.to_i/1000%n=gets.to_i
r=1
k.times{|i|r=r*(n-i)/(i+1)}
p r%10**9