题目描述

整数 $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$ は高々 $1$ つ．

すべてのよい数列 $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 \leq (N+1)/2$，对所有长度为 $N$ 的满足 $0\leq A_i \leq i$ 且正数项两两不同的序列 $A$，求长度为 $K$ 的元素非 0 的下降子序列个数之和。

3 2

1

6 2

660

10 3

242595

100 10

495811864

提示

制約

• $3\ \leq\ N\ \leq\ 5000$
• $2\ \leq\ K$
• $2K-1\ \leq\ N$
• 入力される値はすべて整数

Sample Explanation 1

例えば $A=(0,2,1)$ はよい数列であり，条件を満たす部分列の個数は $1$ です． それ以外のよい数列の例としては $A=(0,1,0),(1,2,3),(0,0,0)$ などが考えられますが，どれも条件を満たす部分列が存在しません． 結局，$A=(0,2,1)$ 以外のよい数列は条件を満たす部分列を持たず，よって答えは $1$ になります．