分数: 1000 点
问题陈述
给你整数 N 和 K。 让我们调用一个整数序列 A=(A_1,A_2,\cdots,A_N) 好 当满足以下所有条件时。
- 0 \leq A_i \leq i (1 \leq i \leq N)
- 对于每个整数 v=1,2,\cdots,N,最多有一个索引 i 这样 A_i=v.
求总和,模 (10^9+7),所有好的序列的以下问题的答案 A.
- 求长度-的数量K (不一定连续)的子序列 A 由递减的正整数组成。换句话说,找到索引序列的数量 1 \leq i_1 < i_2 < \cdots < i_K \leq N 这样 A_{i_1}>A_{i_2}>\cdots>A_{i_K} \geq 1.
约束
- 3 \leq N \leq 5000
- 2 \leq K
- 2K-1 \leq N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K
输出
打印答案。
示例输入 1
3 2
示例输出 1
1
例如, A=(0,2,1) 是一个好的序列,有一个子序列满足条件。 还有其他好的序列,例如 A=(0,1,0),(1,2,3),(0,0,0),但它们都没有满足条件的子序列。 最后除了 A=(0,2,1) 有满足条件的子序列,所以答案是 1.
示例输入 2
6 2
示例输出 2
660
示例输入 3
10 3
示例输出 3
242595
示例输入 4
100 10
示例输出 4
495811864