选定
m
m
m个元素“稳定”,剩余部分错排(即全都不在原本位置)
错排公式
D n = ( n − 1 ) × ( D n − 2 + D n − 1 ) D_n=(n-1)\times(D_{n-2}+D_{n-1}) Dn=(n−1)×(Dn−2+Dn−1)
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#define PII pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define ps push
#define all(a) a.begin(), a.end()
#define pb push_back
#define vec vector
#define str string
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int T;
int fac[N], inv[N], D[N];
void init(int n) {
inv[0] = inv[1] = fac[1] = fac[0] = 1, D[0] = 1, D[1] = 0;
for (int i = 2; i <= n; i++) {
fac[i] = 1LL * fac[i-1] * i % mod;
D[i] = 1LL * (i - 1) * (D[i-2] + D[i-1]) % mod;
inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
}
for (int i = 3; i <= n; i++)
inv[i] = 1LL * inv[i] * inv[i-1] % mod;
return ;
}
inline int C(int n, int m) {
return 1LL * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
inline int slove(int n, int m) {
if (n < m) return 0;
return 1LL * C(n, m) * D[n - m] % mod;
}
int main() {
init(N - 10);
for (scanf("%d", &T); T--; ) {
int n, m; scanf("%d%d", &n, &m);
printf("%d\n", slove(n, m));
}
return 0;
}