E - Erasure

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700

問題文

1 から N までの番号のついた N 個のブロックがあります。 また、整数 K が与えられます。

魔法使いのコウさんは、魔法を唱えてこれらのブロックを消し去ろうとしています。 彼は、以下のような魔法を唱えることができます。

  • 1 \leq l \leq r \leq N, r-l \geq K を満たす整数の組 (l,r) を選び、 番号が l 以上 r 以下の(まだ消されていない)ブロックをすべて消す。

つまり、彼が唱えられる魔法は (l,rの選び方の総数) =(N-K) \times (N-K+1) / 2 種類あります。

それぞれの魔法を唱えるか唱えないかの組み合わせは全部で 2^{(N-K) \times (N-K+1) / 2} 通りあります。 コウさんは、このうち最終的にブロックをすべて消し去ることのできる組み合わせが何通りあるかに興味を持っています。

コウさんのために、最終的にブロックをすべて消し去ることのできる組み合わせが何通りあるかを求めてください。 ただし、答えは非常に大きくなることがあるので、答えを 10^9+7 で割ったあまりを求めてください。

制約

  • 1 \leq N \leq 5000
  • 0 \leq K \leq N-1
  • 入力される値はすべて整数である。

入力

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

N K

出力

最終的にブロックをすべて消し去ることのできる組み合わせの個数を 10^9+7 で割ったあまりを出力せよ。


入力例 1

3 1

出力例 1

5

コウさんが唱えられる魔法は、(l,r)=(1,2),(2,3),(1,3)3 種類です。 最終的にブロックをすべて消し去ることのできる組み合わせは、以下の 5 通りです。

  • (1,2)(2,3)
  • (1,2)(1,3)
  • (1,2)(2,3)(1,3)
  • (2,3)(1,3)
  • (1,3)

入力例 2

10 5

出力例 2

30784

入力例 3

5000 250

出力例 3

844653816