P2513 [HAOI2009] Inversion Count Sequence

For a sequence $\{a_i\}$, if $i < j$ and $a_i > a_j$, then we call $a_i$ and $a_j$ an inversion pair. For any sequence formed by the natural numbers $1 \sim n$ (i.e., a permutation), it is easy to compute how many inversions it has. How many such sequences have exactly $k$ inversions?

The first line contains two integers $n, k$.

Output a single integer: the number of sequences that satisfy the condition. Since this number can be very large, you only need to output the result modulo $10000$.

【Sample Explanation】 The following $3$ sequences each have exactly $1$ inversion: $\{1,2,4,3\}$; $\{1,3,2,4\}$; $\{2,1,3,4\}$. Constraints - For $30\%$ of the testdata, $n \le 12$. - For $100\%$ of the testdata, $n \le 1000$, $k \le 1000$. Translated by ChatGPT 5