Ａ君は、全国数学コンクールに応募するための自由研究に取り組んでいる。今年のテーマは「美しい数列」。Ａ君は、コンピュータの仕組みに興味を持っており、0 と 1 のみを含む長さ $N$ の数列において、1が $M$ 個連続する部分列を含む数列を「美しい数列」と定義し、作品を作ることにした。
Ａ君は得意のプログラミングで、異なる「美しい数列」がいくつ作れるかを計算し、レポートにまとめることにした。
数列の長さ $N$ と、1 が連続する個数 $M$ を入力とし、美しい数列の個数を求めるプログラムを作成せよ。ただし、答えは非常に大きくなる場合があるため、$1000000007 (=10^9+7)$で割った余りを出力せよ。
入力
入力は以下の形式で与えられる。
$N$ $M$
１行に数列の長さ$N$ ($1 \leq N \leq 10^5$)と、1が連続する個数$M$ ($1 \leq M \leq N$) が与えられる。
出力
美しい数列の個数を１行に出力する。
入出力例
入力例１
4 3
出力例１
3
長さが 4 で 1 が３個連続する数列は、0111、1110、1111 である。
入力例２
4 2
出力例２
8
長さが 4 で 1 が２個連続する数列は、0011、0110、0111、1011、1100、1101、1110、1111 である。