#P5255. [Fjwc2018]全排列

    ID: 4293 传统题 2000ms 512MiB 尝试: 79 已通过: 40 难度: 7 上传者: 标签>CF2200提高贡献法计数 DP前缀和优化 DP阶乘逆元预处理离线查询滚动数组ByExfJoe

[Fjwc2018]全排列

[FJWC2018] 全排列

题目描述

定义两个长为 nn 的排列 AA 与 BB 相似:若 ∀i\forall i,满足 C(A,Ai)=C(B,Bi)C(A, A_i) = C(B, B_i)。其中 C(P,x)C(P, x) 为满足 Pj<xP_j < x (1⩽j⩽n)(1 \leqslant j \leqslant n) 的 jj 的数目。

对于两个长为 nn 的排列 P1,P2P_1, P_2,定义函数 F(P1,P2)F(P_1, P_2) 等于满足 P1[l…r]P_1[l \ldots r] 相似于 P2[l…r]P_2[l \ldots r] (1⩽l⩽r⩽n)(1 \leqslant l \leqslant r \leqslant n) 并且 P1[l…r]P_1[l \ldots r] 包含不超过 EE 个逆序对的数对 (l,r)(l, r) 的数目。

现在请你求出:对 P1,P2P_1, P_2 分别取遍所有 1∼n1 \sim n 的排列后所有 F(P1,P2)F(P_1, P_2) 的和。

输入格式

第一行一个整数 TT 表示数据组数。

接下来 TT 行,每行包含两个非负整数 n,En, E。

输出格式

对于每组数据,输出一行一个整数表示答案模 109+710^9 + 7。

样例 #1

样例输入 #1

4
2 2
2 1
2 0
1 1

样例输出 #1

10
10
9
1

提示

对于 50%50\% 的数据,T⩽104,n⩽10,E⩽50T \leqslant 10^4, n \leqslant 10, E \leqslant 50。

对于 80%80\% 的数据,T⩽104,n⩽50,E⩽106T \leqslant 10^4, n \leqslant 50, E \leqslant 10^6。

对于 100%100\% 的数据,$T \leqslant 10^4, n \leqslant 500, E \leqslant 10^6$。