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