C. 排列计数(错排)

Description

求有多少种长度为n的序列A，满足以下条件：

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

若第i个数A[i]的值为i，则称i是稳定的。序列恰好有m个数是稳定的满足条件的序列可能很多，序列数对109+7取模。

Input

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

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

T=500000，n≤1000000，m≤1000000

Output

输出T行，每行一个数，表示求出的序列数

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define
#define
#define
#define
#define
#define
const int maxn=1e6+10;
#define
#define
#define
const int mod=1e9+7;
const int MOD=1e9+7;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

vector<ll> m1;
vector<ll> m2;
priority_queue<ll, vector<ll>, greater<ll> > mn;  //上  小根堆        小到大
priority_queue<ll, vector<ll>, less<ll> > mx;  //下     大根堆     大到小
map<ll,ll>mp;
ll n,m,p;
ll fac[maxn];
ll infac[maxn];
ll cuo[maxn];
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int main() {
    ll t;
    cin>>t;
    fac[0]=1;
    fac[1]=1;
    for(int i=2;i<=1000000;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    infac[0]=1;
    infac[1000000]=qpow(fac[1000000],mod-2);
    for(int i=999999;i>0;i--){
        infac[i]=infac[i+1]*(i+1)%mod;
    }
    cuo[0]=1;cuo[1]=0;cuo[2]=1;
    for(int i=3;i<=1000000;i++){
        cuo[i]=((i-1)*((cuo[i-1]+cuo[i-2])%mod))%mod;
    }

    while(t--){
        scanf("%lld%lld",&n,&m);
       ll ans=fac[n]*infac[m]%mod*infac[n-m]%mod*cuo[n-m]%mod;
        printf("%lld\n",ans);
    }
    return 0;
}