Typical DP Contest

F - 準急


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 262.144MB

Problem Statement

ある路線には駅 1 から駅 N までの N 個の駅がある。すぬけ君は、この路線に準急を走らせることにした。
  • 準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。
  • 連続する K個以上の駅に止まると、客が飽きてしまうので、そのようなことはしない。
準急の停車駅の組み合わせとして何通り考えられるか、mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ K ≤ N ≤ 1000000

Input Format

入力は以下の形式で標準入力から与えられる。
N K

Output Format

答えを一行に出力せよ。

Sample Input 1

10 2

Sample Output 1

21

Sample Input 2

10 10

Sample Output 2

255

Submit提出する