Problem
バッタは、同じ線上にある等距離にある列にジャンプします。列には 1 から N までのシリアル番号が付いています。最初に、バッタは番号 1 の柱に座っています。現在のバーから数えて、1 から K バーまで前方にジャンプできます。グラスホッパーが番号 N の列に到達できる方法の数を見つける必要があります。バッタは後ろにジャンプできないことに注意してください。
見つける方法の数は非常に多くなる可能性があるため、モジュロ \(10^6 + 7\) 、つまり、除算の剰余を見つけて、この数を\(10^6 + 7\) .
入力: 入力文字列には、スペースで区切られた自然数 N と K が含まれます。 \(1 <= N ,\ K <= 10000\) であることが保証されています。
出力: プログラムは 1 つの数値を出力する必要があります: 計算された N 番号の列にグラスホッパーが到達できる方法の数モジュールから \(10^6+7\).
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |