[HAOI2009]逆序对数列

对于一个数列 $\{a_i\}$，若存在 $i<j$ 且 $a_i>a_j$，则称 $(a_i,a_j)$ 为一对逆序对。

给定整数 $n$ 和 $k$，求由 $1$ 到 $n$ 这 $n$ 个自然数组成、且恰好包含 $k$ 个逆序对的排列数量。

输入格式

一行两个整数 $n$ 和 $k$。

输出格式

输出一个整数，表示符合条件的排列数量。由于答案可能很大，请输出答案对 $10^4$ 取模后的结果。

样例输入

4 1

样例输出

3

数据范围

• 原题未给出明确的数据范围。

来源与许可

本题为 HAOI 2009 试题「逆序对数列」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 1

输出

3