$$【组合数学】专题笔记目录$$

考虑先满足 $m$ 个位置 $a_i=i$，相当于 $n$ 个位置选 $m$ 个，方案数为 $C_n^m$。
再考虑让剩下 $n-m$ 个位置错排，即不能让任意位置满足 $a_i=i$。怎么求方案数呢？

令 $d_x$ 表示 $x$ 个位置错排的方案数。
从第一个位置考虑，它可以放在 2...x 的 $x-1$ 个位置上，方案数为 $x-1$。
那剩下的成为了一个子问题：设第一个数放在位置 $i$ ，则有两种情况：

• $i$ 放在位置 $1$，则相当于原问题减去 $1$ 和 $i$ 两个位置，方案数为 $d_{x-2}$。
• $i$ 放在其它任意位置，则相当于把 $i$ 这个位置限制不能放在 $1$，原问题减去 $1$ 这个位置，方案数为 $d_{x-1}$。

由此得到递推式 $d_i = (i-1) \times (d_{i-2} + d_{i-1})$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15;
const int mod = 1e9 + 7;
int T, n, m;

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

long long fac[N], inv[N], d[N];

void init() {
    d[0] = 1, d[1] = 0;
    for (int i = 2; i <= 1000000; i++) d[i] = ((i - 1) * 1ll * (d[i - 1] + d[i - 2])) % mod;
    fac[0] = 1;
    for (int i = 1; i <= 1000000; i++) fac[i] = (fac[i - 1] * 1ll * i) % mod;
    inv[1000000] = qmi(fac[1000000], mod - 2);
    for (int i = 999999; i >= 0; i--) inv[i] = (inv[i + 1] * 1ll * (i + 1)) % mod;
}

int main() {
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        printf("%d\n", (fac[n] * inv[m] % mod * inv[n - m] % mod * d[n - m] + mod) % mod);
    }
    return 0;
}