题目描述

求有多少长度为$n$的序列$A$,满足以下条件:

$1 - n$ 这$n$个数在序列中各出现了一次。

若第$i$个数$A[i]$的值为$i$,则称$i$是稳定的。序列恰好有$m$个数是稳定的。

满足条件的序列可能很多,序列数对$10 ^ 9 + 7$取模。

输入格式

第一行一个数$T$,表示有$T$组数据。

接下来$T$行,每行两个整数$n,m$。

输出格式

输出$T$行,每行一个数,表示求出的序列数。

题目解析

考虑$n$个位置选$m$个位置为稳定点，其它$n-m$个位置错排，有

$$ans = {n \choose m} D(n - m)$$

组合数线性预处理逆元即可。时间复杂度$O(n + T)$。