{"problem":{"name":"Decreasing Subsequence","description":{"content":"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$) *   Fo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc138_e"},"statements":[{"statement_type":"Markdown","content":"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.\n\n*   $0 \\leq A_i \\leq i$ ($1 \\leq i \\leq N$)\n*   For every integer $v=1,2,\\cdots,N$, there is at most one index $i$ such that $A_i=v$.\n\nFind the sum, modulo $(10^9+7)$, of the answers to the following problem for all good sequences $A$.\n\n*   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$.\n\n## Constraints\n\n*   $3 \\leq N \\leq 5000$\n*   $2 \\leq K$\n*   $2K-1 \\leq N$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc138_e","tags":[],"sample_group":[["3 2","1\n\nFor 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$."],["6 2","660"],["10 3","242595"],["100 10","495811864"]],"created_at":"2026-03-03 11:01:13"}}