题目描述

我们说$(i,j)$ 是 $a_1,a_2,\cdots,a_N$ 的一个逆序对，当且仅当 $i<j$ 且 $a_i>a_j$。例如 $[2,4,1,3,5]$ 的逆序对有 $3$ 个，分别为 $(1,3),(2, 3), (2, 4)$。现在已知 $N$ 和 $K$，求 $1,2,3,\cdots,N$ 的所有特定排列，使得这些排列的逆序对的数量恰好为 $K$。输出这些特定排列的数量。

例如 $N=5$，$K=3$ 的时候，满足条件的排列有 $15$ 个，它们是：

• $[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]$。

输入格式

输入共第一行，两个整数 $N$ 和 $K$。

输出格式

将 $1\cdots N$ 的逆序对数量为 $K$ 的特定排列的数量输出。为了避免高精度计算，请将结果对 $10000$ 取模后再输出。

5 3

15

提示

数据范围及约定

对于全部数据，保证 $N \le 100$，$K \le N\times (N-1)/2$。