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