#P15866. [Roi2024 Team]Exchange and Deletion交换与删除

    ID: 15077 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高不变量分析对称性分析加法原理乘法原理排列数计算阶乘逆元预处理快速幂

[Roi2024 Team]Exchange and Deletion交换与删除

题目描述

从数组中删除一个元素有一种经典方法:把要删除的元素和数组最后一个元素交换,然后删除最后一个元素。可惜,这种删除方法不一定能保持数组有序。

初始数组 aa 长度为 nn,并且

ai=i.a_i=i.

另有一个长度为 kk 的数组 bb,其中元素是 11 到 nn 之间两两不同的数。

接下来进行 kk 步操作。第 jj 步时,找到当前数组中值等于 bjb_j 的位置 ii,将 aia_i 与当前最后一个元素交换,然后删除最后一个元素。

如果执行完这 kk 步后,剩余数组严格递增,则称数组 bb 是好的。

给定 nn 和 kk,请你求好的数组 bb 有多少个。答案对 109+710^9+7 取模。

输入格式

第一行输入整数 tt,表示测试数据组数。

1≤t≤1041 \le t \le 10^4

接下来 tt 行,每行两个整数 n,kn,k。

1≤n≤5⋅105,1 \le n \le 5\cdot 10^5, 0≤k≤n.0 \le k \le n.

所有测试数据中 nn 的总和不超过 5⋅1055\cdot 10^5。

输出格式

对每组数据输出一个整数,表示好的数组数量,结果对 109+710^9+7 取模。

样例

5
1 0
1 1
2 2
3 1
4 2
1
1
2
2
7