我不理解，为什么第二个样例只有 331。

我的思路：

$k$ 个操作，如果 $r=c,n-=1,r\neq c, n-=2$。

然后枚举对角选几个。$\binom{n}{i}$。

设 $cnt[x]$ 表示 $x\times x$ 的矩阵，不选对角时的选法。

$cnt[x]=(2\times i-2)\times cnt[x-2](x\&1==0)$

$cnt[x]=(2\times i-2)\times cnt[x-2]+cnt[x-1](x\&1==1)$

这样算出来，$cnt[5]=60,cnt[4]=12,cnt[3]=6$

这样的话，我第二个样例，选两个对角，算出来 $12\times 15=180$ 明显比答案大。

但是我不理解为什么。

这个思路哪里有问题呢？

#include<bits/stdc++.h>
// #pragma GCC optimize ("O2")
#define int long long
#define ldb long double 
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int N=5e5+10,mod=1e9+7;
int n,k;
int fac[N],inv[N],Ans[N];
int qz(int x,int y){
    if(y<0) return 1;
    int res=1;
    for(;y;y>>=1){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
    }
    return res;
}
int qz(int x,int y,int mod){
    int res=1;
    for(;y;y>>=1){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
    }
    return res;
}
void init(int n){
    int i;
    fac[0]=inv[0]=1;
    For(i,1,n) fac[i]=fac[i-1]*i%mod;
    inv[n]=qz(fac[n],mod-2);
    FOR(i,n-1,1) inv[i]=inv[i+1]*(i+1)%mod;
    Ans[1]=1;
    Ans[2]=2;
    For(i,3,n)
        if(i%2==0)
            Ans[i]=(2*i-2)*Ans[i-2]%mod;
        else
            Ans[i]=((2*i-2)*Ans[i-2]%mod+Ans[i-1])%mod;
}
int C(int x,int y){
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void solve(){
    int i,ans=1;
    For(i,0,n-2){
        int len=n-i;
        ans=(ans+C(n,i)*Ans[len]%mod)%mod;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init(3e5);
    int i,t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        For(i,1,k){
            int x,y;
            cin>>x>>y;
            if(x==y) n--;
            else n-=2;
        }
        solve();
    }
    return 0;
}