問題一覧 > 通常問題

No.129 お年玉(2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 242
作問者 : yuki2006
4 ProblemId : 143 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-08-16 19:15:00

問題文

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

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

準備として、すべてのお年玉袋に、平等で最大な額の1000円紙幣を入れた後に、予算が余っているなら、「当たり」として、
1つの同じ袋には、1000円をいれるかいれないかとして、ランダムにそれぞれのお年玉袋に追加で振り分けることにした。

この時、誰がどのお年玉袋がもらえるかはわからないとして、
M人のそれぞれのもらえるお年玉の額の組み合わせは、何通りあるか求めてください。
1000円紙幣にできるなら余りを全て使うものとする。
答えが非常に大きくなるので1000000000=109(素数ではないことに注意)で割った余りを求めてください。

入力

N
M

入力は全て整数で与えられる。
1N10000000000000000=1016
1M10000=104

出力

お年玉の額の組み合わせは、何通りあるかを1000000000=109で割った余りを求めてください。
最後に改行をしてください。

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。