当x!=y时，这个限制条件是确定的，可以枚举总通过数，用组合数计算，当x==y时，这个限制条件表示前x个全部通过或后x个全部通过，只有最大的x有用，可以用容斥计算。
#include<bits/stdc++.h>
const int P=;
int T,n,m,pp[],C[][];
struct pos{
int x,y,t;
bool operator<(pos p)const{return x<p.x;}
}ps[][];
void ins(pos p){
for(int i=;i<;++i)ps[i][pp[i]++]=p;
}
int cal(int w,int m){
pos*a=ps[w];
int ap=pp[w],s=;
for(int i=;i<ap;++i){
int v1=a[i].x-a[i-].x,v2=a[i].y-a[i-].y+(a[i].t-a[i-].t)*m;
if(v2<||v2>v1)return ;
s=1ll*s*C[v1][v2]%P;
}
return s;
}
int main(){
C[][]=;
for(int i=;i<;++i){
for(int j=;j<=i;++j){
(C[i+][j]+=C[i][j])%=P;
(C[i+][j+]+=C[i][j])%=P;
}
}
for(scanf("%d",&T);T;--T){
scanf("%d%d",&n,&m);
int mx=-;
pp[]=pp[]=pp[]=;
ins((pos){,,});
ins((pos){n,,});
for(int i=,a,b;i<m;++i){
scanf("%d%d",&a,&b);
if(a>b)ins((pos){a,b,});
else if(a<b)ins((pos){n-b,-a,});
else{
if(a>mx)mx=a;
}
}
if(~mx){
ps[][pp[]++]=(pos){n-mx,-mx,};
ps[][pp[]++]=(pos){mx,mx,};
ps[][pp[]++]=(pos){mx,mx,};
ps[][pp[]++]=(pos){n-mx,-mx,};
}
for(int i=;i<;++i)std::sort(ps[i],ps[i]+pp[i]);
int ans=;
for(int i=;i<=n;++i){
int sgn[]={,,-};
for(int j=;j<;++j){
ans=(ans+cal(j,i)*sgn[j])%P;
}
}
printf("%d\n",(ans+P)%P);
}
return ;
}