未提交，因为没过样例，样例第3组数据输出432943110，望大佬解答

#include <bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
int n,k,r,c,t,tot=2;
long long dp[300005];
int main(){
	dp[0]=1,dp[1]=1,dp[2]=3;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		for(int i=1;i<=k;i++){
			scanf("%d%d",&r,&c);
			if(r==c) n-=1;
			else n-=2;
		}
		if(n<=tot) printf("%lld\n",dp[n]);
		else{
			for(tot=tot+1;tot<=n;tot++){
				dp[tot]=(dp[tot-1]+(2*tot-2)*dp[tot-2]%MOD)%MOD;
			}
			printf("%lld\n",dp[n]);
		}
	}
	return 0;
}