050 - Stair Jump(★3)
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点:3 点
問題文
E869120 君は、N 段の階段を上ろうとしています。彼は一歩で 1 段か L 段上ることができます。
0 段目から出発し、N 段目にたどり着くまでの移動方法が何通りあるかを求め、10^9 + 7 で割った余りを出力してください。
制約
- 2 \leq N \leq 100000
- 2 \leq L \leq 100000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N L
出力
答えを 1 行に出力してください。
入力例 1
3 2
出力例 1
3
移動方法は、以下のような 3 通りの方法があります。
- 1 段上る → 1 段上る → 1 段上る
- 1 段上る → 2 段上る
- 2 段上る → 1 段上る
入力例 2
4 4
出力例 2
2
1 段ずつ上る方法と、一気に 4 段を上る方法があります。
入力例 3
5 2
出力例 3
8
入力例 4
6783 125
出力例 4
674508908
10^9 + 7 で割った余りを出力することに注意してください。