F - 準急 解説

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

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

Constraints

  • 2≤K≤N≤10000002 ≤ K ≤ N ≤ 1000000

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

10 2

Sample Output 1

21

Sample Input 2

10 10

Sample Output 2

255

2025-04-03 (木)
14:53:49 +00:00