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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定 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}