清北学堂模拟赛day7 错排问题

/*

考虑一下已经放回m本书的情况，已经有书的格子不要管他，考虑没有书的格子，不考虑错排有(n-m)!种，在逐步考虑有放回原来位置的情况，已经放出去和已经被占好的格子，不用考虑，剩下全都考虑，设t=x∩y，把除t以外的搞一下容斥就行了

*/

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#define ll long long

#define fo(i,l,r) for(int i = l;i <= r;i++)

#define fd(i,l,r) for(int i = r;i >= l;i--)

using namespace std;

const int maxn = ;

const ll mod = 1000000007LL;

ll read(){

    ll x=,f=;

    char ch=getchar();

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};

    return x*f;

}

ll n,m,x[maxn],y[maxn],rec[maxn],c[maxn];

bool usd[maxn];

ll ans,fac[maxn];

ll q_pow(ll a,ll b){

    ll ret = ;

    while(b){

        if(b&) ret = (ret*a) % mod;

        a = (a*a) % mod;

        b >>= ;

    }

    return ret;

}

inline ll inv(ll x){

    return q_pow(x,mod-);

}

int main(){

    freopen("problem.in","r",stdin);

    freopen("problem.out","w",stdout);

    n = read();m = read();

    fo(i,,m) x[i] =read(),y[i]=read();

    fo(i,,m){

        usd[x[i]] = true;

        usd[y[i]] = true;

    }

    int t = n;

    fo(i,,n) if(usd[i]) t--;

    fac[] = fac[] = ;

    fo(i,,n) fac[i] = (fac[i-]*i) % mod;

    c[] = c[t] = ;

    if(t > ) c[] = c[t-] = t;

    fo(i,,t-)c[i] = ((c[i-]*(t-i+)%mod)*inv(i))%mod;

    ans = fac[n-m];

    fo(i,,t){

        if(i&) ans = (ans + *mod - (c[i]*fac[n-m-i]) % mod) % mod;

        else ans = (ans + (c[i]*fac[n-m-i]) % mod) % mod;

    }

    cout<<ans;

    return ;

}