Description

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?

Input Format

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

Output Format

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$.

4 1

3

Hint

【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