/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 について，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 を満たすものの個数を求めよ．
制約
- 3 \leq N \leq 5000
- 2 \leq K
- 2K-1 \leq N
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N K
出力
答えを出力せよ．
入力例 1
3 2
出力例 1
1
例えば A=(0,2,1) はよい数列であり，条件を満たす部分列の個数は 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
Score : 1000 points
Problem Statement
You are given integers N and K. Let us call an integer sequence A=(A_1,A_2,\cdots,A_N) good when it satisfies all of the conditions below.
- 0 \leq A_i \leq i (1 \leq i \leq N)
- For every integer v=1,2,\cdots,N, there is at most one index i such that A_i=v.
Find the sum, modulo (10^9+7), of the answers to the following problem for all good sequences A.
- Find the number of length-K (not necessarily contiguous) subsequences of A consisting of positive integers that are decreasing. In other words, find the number of sequences of indices 1 \leq i_1 < i_2 < \cdots < i_K \leq N such that A_{i_1}>A_{i_2}>\cdots>A_{i_K} \geq 1.
Constraints
- 3 \leq N \leq 5000
- 2 \leq K
- 2K-1 \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the answer.
Sample Input 1
3 2
Sample Output 1
1
For example, A=(0,2,1) is a good sequence, with one subsequence satisfying the condition. There are other good sequences such as A=(0,1,0),(1,2,3),(0,0,0), but none of them has subsequences satisfying the condition. In the end, no good sequence other than A=(0,2,1) has subsequences satisfying the condition, so the answer is 1.
Sample Input 2
6 2
Sample Output 2
660
Sample Input 3
10 3
Sample Output 3
242595
Sample Input 4
100 10
Sample Output 4
495811864