No.129 お年玉(2)
yuki2006問題文
Yasuoは、予算が$N$円しかないが、親戚の子供$M$人にお年玉をあげたいと思っている。
お年玉の中に入れる種類は$1000$円紙幣だけにしたいと思っているが、なるべく平等でかつ最大の金額をあげたいと思っています。
今回は、前回のように配って予算が余った分も配り「当たり」とすることにした。
準備として、すべてのお年玉袋に、平等で最大な額の$1000$円紙幣を入れた後に、予算が余っているなら、「当たり」として、
１つの同じ袋には、$1000$円をいれるかいれないかとして、ランダムにそれぞれのお年玉袋に追加で振り分けることにした。
この時、誰がどのお年玉袋がもらえるかはわからないとして、
$M$人のそれぞれのもらえるお年玉の額の組み合わせは、何通りあるか求めてください。
1000円紙幣にできるなら余りを全て使うものとする。
答えが非常に大きくなるので$1000000000=10^9$（素数ではないことに注意）で割った余りを求めてください。
入力
N M
入力は全て整数で与えられる。
$1\le N \le 10000000000000000=10^{16}$
$1\le M \le 10000=10^{4}$
出力
お年玉の額の組み合わせは、何通りあるかを$1000000000=10^9$で割った余りを求めてください。
最後に改行をしてください。
サンプル
サンプル1
入力
10000 5
出力
1
予算が$10000$円あり、$5$人に配るので全員$1$人あたり平等に$2000$円です。
（つまり1通り）
サンプル2
入力
24500 9
出力
84
$1000$円紙幣分を平等に配ると$6500$円分あまるが、残りを$1000$円紙幣にできるのは$6000$円分である。
余った分をランダムに配る。
すると$84$通りの配り方がある。
サンプル3
入力
1800 6
出力
6
$6$人のうち誰かが$1000$円ゲットです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。