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

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

题目描述

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

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

输入格式

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

输出格式

一行,表示答案。

样例

样例输入

7 12

样例输出

531

数据范围与提示

对于 20% 20\% 20% 的数据,n,k≤20 n, k \leq 20 n,k20
对于 40% 40\% 40% 的数据,n,k≤100 n, k \leq 100 n,k100
对于 60% 60\% 60% 的数据,n,k≤5000 n, k \leq 5000 n,k5000
对于 100% 100\% 100% 的数据,1≤n,k≤100000,1≤k≤(n2) 1 \leq n, k \leq 100000, 1 \leq k \leq \binom{n}{2} 1n,k100000,1k(2n)