Description

We call $(i, j)$ an inversion of $a_1, a_2, \cdots, a_N$ if and only if $i < j$ and $a_i > a_j$. For example, $[2, 4, 1, 3, 5]$ has 3 inversions: $(1, 3), (2, 3), (2, 4)$. Now given $N$ and $K$, find the number of permutations of $1, 2, 3, \cdots, N$ whose number of inversions is exactly $K$. Output that count.

For example, when $N = 5$, $K = 3$, there are 15 valid permutations. They are:

• [1, 2, 5, 4, 3].
• [1, 3, 4, 5, 2].
• [1, 3, 5, 2, 4].
• [1, 4, 2, 5, 3].
• [1, 4, 3, 2, 5].
• [1, 5, 2, 3, 4].
• [2, 1, 4, 5, 3].
• [2, 1, 5, 3, 4].
• [2, 3, 1, 5, 4].
• [2, 3, 4, 1, 5].
• [2, 4, 1, 3, 5].
• [3, 1, 2, 5, 4].
• [3, 1, 4, 2, 5].
• [3, 2, 1, 4, 5].
• [4, 1, 2, 3, 5].

Input Format

The first line contains two integers $N$ and $K$.

Output Format

Output the number of permutations of $1 \cdots N$ whose number of inversions is $K$. To avoid big integer arithmetic, output the result modulo $10000$.

5 3

15

Hint

Constraints

For all testdata, it is guaranteed that $N \le 100$, $K \le N \times (N - 1) / 2$.

Translated by ChatGPT 5