007 - 美しい数列

時間制限 1 秒 / メモリ制限 256 MB / 得点 10 / x 0 /


TLE
1sec
MLE
256MB
得点
10

A君は、全国数学コンクールに応募するための自由研究に取り組んでいる。今年のテーマは「美しい数列」。A君は、コンピュータの仕組みに興味を持っており、0 と 1 のみを含む長さ $N$ の数列において、1が $M$ 個連続する部分列を含む数列を「美しい数列」と定義し、作品を作ることにした。

A君は得意のプログラミングで、異なる「美しい数列」がいくつ作れるかを計算し、レポートにまとめることにした。

数列の長さ $N$ と、1 が連続する個数 $M$ を入力とし、美しい数列の個数を求めるプログラムを作成せよ。ただし、答えは非常に大きくなる場合があるため、$1000000007 (=10^9+7)$で割った余りを出力せよ。

入力

入力は以下の形式で与えられる。

$N$ $M$  

1行に数列の長さ$N$ ($1 \leq N \leq 10^5$)と、1が連続する個数$M$ ($1 \leq M \leq N$) が与えられる。

出力

美しい数列の個数を1行に出力する。

入出力例

入力例1

4 3

出力例1

3

長さが 4 で 1 が3個連続する数列は、0111、1110、1111 である。

入力例2

4 2

出力例2

8

長さが 4 で 1 が2個連続する数列は、0011、0110、0111、1011、1100、1101、1110、1111 である。