Description：

求有多少种长为 $n$ 的排列满足恰好有 $m$ 个 $a[i]=i$ 的数。

$1\le n\le 1000000,1\le t\le 500000$

Solution：

先选出 $m$ 个，有 $C_m^n$ 种选法，可以预处理阶乘及其逆元 $O(1)$ 计算，剩下的每个都不能在自己位置，相当于是一个错位排列，根据错位排列递推式 $d[i]=(i-1)\times(d[i-1]+d[i-2])$ ，答案就是 $C_m^n\times d[n-m]$ 。关于错位排列递推式：可以这样理解，对于每一个位置 $k$ ，如果 $n$ 在 $k$ ， $k$ 在 $n$ ，那剩下的就是一个错排，方案为 $d[i-2]$ ，如果 $k$ 不在 $n$ ，那么可以把第 $n$ 位看成第 $k$ 位，是一个 $i-1$ 的错排，这样的 $k$ 有 $i-1$ 种取值。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000007

#define MAXN 1000001

typedef long long ll;

ll d[MAXN];

ll n,m;

ll fac[MAXN],inv[MAXN];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

ll C(ll n,ll m)

{

	return fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

int main()

{

	d[0] = 1;d[1] = 0;d[2] = 1;

	for(ll i = 3;i < MAXN;++i)d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % MOD;

	fac[0] = 1;

	for(ll i = 1;i < MAXN;++i)fac[i] = fac[i - 1] * i % MOD;

	inv[MAXN - 1] = power(fac[MAXN - 1],MOD - 2);

	for(int i = MAXN - 2;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % MOD;

	int testcases;

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		scanf("%lld%lld",&n,&m);

		cout << C(n,m) * d[n - m] % MOD << endl;

	}

	return 0;

}