201384: [AtCoder]ARC138 E - Decreasing Subsequence
Memory Limit:1024 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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