$k=<>/1e3%($M=<>);
for$n(0..$M){
	$C[$n][$_]=($C[$n-1][$_-1]+$C[$n-1][$_])%1e9for($C[$n][0]=1)..$n
}
print$C[$M][$k]