← 返回题目列表

AtCoder · nikkei2019_final_e

E. 删除

中文机器翻译题面 查看原题

配点 : 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