AT_arc138_e.[ARC138E] Decreasing Subsequence

给定整数 $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$，使得 $A_i=v$ 的 $i$ 最多只有一个。

对于所有好数列 $A$，请计算以下问题的答案之和，并对 $10^9+7$ 取模。

• 求 $A$ 的长度为 $K$ 的（不一定连续的）子序列中，仅包含正整数且严格单调递减的子序列的个数。换句话说，求满足 $1 \leq i_1 < i_2 < \cdots < i_K \leq N$ 且 $A_{i_1} > A_{i_2} > \cdots > A_{i_K} \geq 1$ 的方案数。

输入从标准输入读入，格式如下：

$N$ $K$

请输出答案。

限制条件

• $3 \leq N \leq 5000$
• $2 \leq K$
• $2K-1 \leq N$
• 输入的所有值均为整数

样例解释 1

例如 $A=(0,2,1)$ 是一个好数列，满足条件的子序列个数为 $1$。其他好数列如 $A=(0,1,0)$、$A=(1,2,3)$、$A=(0,0,0)$ 等都没有满足条件的子序列。最终，除了 $A=(0,2,1)$ 以外的好数列都没有满足条件的子序列，因此答案为 $1$。

由 ChatGPT 4.1 翻译