[AdditionalFile6077.zip](file://AdditionalFile6077.zip?type=additional_file)

#6077. 「2017 山东一轮集训 Day7」逆序对

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

给定 $n, k$，请求出长度为 $n$ 的逆序对数恰好为 $k$ 的排列的个数。答案对 $10 ^ 9 + 7$ 取模。

对于一个长度为 $n$ 的排列 $p$，其逆序对数即满足 $i < j$ 且 $p_i > p_j$ 的二元组 $(i, j)$ 的数量。

输入格式

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

输出格式

一行，表示答案。

样例

输入

7 12

输出

531

数据范围与提示

对于 $20\%$ 的数据，$n, k \leq 20$；
对于 $40\%$ 的数据，$n, k \leq 100$；
对于 $60\%$ 的数据，$n, k \leq 5000$；
对于 $100\%$ 的数据，$1 \leq n, k \leq 100000, 1 \leq k \leq \binom{n}{2}$。