No.129 お年玉(2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 104
作問者 : yuki2006yuki2006

1 ProblemId : 143 / 出題時の順位表

問題文

Yasuoは、予算が$N$円しかないが、親戚の子供$M$人にお年玉をあげたいと思っている。
お年玉の中に入れる種類は$1000$円紙幣だけにしたいと思っているが、なるべく平等でかつ最大の金額をあげたいと思っています。

今回は、前回のように配って予算が余った分も配り「当たり」とすることにした。

準備として、すべてのお年玉袋に、平等で最大な額の$1000$円紙幣を入れた後に、予算が余っているなら、「当たり」として、
1つの同じ袋には、$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$円ゲットです。

提出ページヘ