#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;
int T,n,m,v2[50003][2],v3[50003][2],k1,k2,k3,k4,k5,k6,k7,k8,k9,ans;
int dp[5003][5003],hsum[5003],lsum[5003];
int q[100003],lft,rgt,zz[50003];
void del(int X){
	for(int i=0;i<=X-2;i++){
		if(i>=v3[X][0]&&i<=v3[X][1])continue;
		hsum[i]=0;
		while(zz[i]<X){
			lsum[zz[i]]=(lsum[zz[i]]-dp[i][zz[i]])%MOD;
			dp[i][zz[i]]=0;
			zz[i]++;
		}
	}
	while(lft<=rgt){
		if(q[lft]>=v2[X][0])break;
		lsum[q[lft]]=0;
		for(int j=0;j<=n;j++){
			hsum[j]=(hsum[j]-dp[j][q[lft]])%MOD;
			dp[j][q[lft]]=0;
		}
		lft++;
	}
	while(lft<=rgt){
		if(q[rgt]<=v2[X][1])break;
		lsum[q[rgt]]=0;
		for(int j=0;j<=n;j++){
			hsum[j]=(hsum[j]-dp[j][q[rgt]])%MOD;
			dp[j][q[rgt]]=0;
		}
		rgt--;
	}
	return;
}
void add(int X,int Y,int val){
	hsum[X]=(hsum[X]+val)%MOD;
	lsum[Y]=(lsum[Y]+val)%MOD;
	dp[X][Y]=(dp[X][Y]+val)%MOD;
	return;
}
int stk[50003];
void sol(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		v3[i][0]=0;
		v3[i][1]=i+1;
		v2[i][0]=0;
		v2[i][1]=i+1;
	}
	for(int i=1;i<=m;i++){
		cin>>k1>>k2>>k3;
		if(k3==1)v2[k2][1]=min(v2[k2][1],k1-1);
		if(k3==2){
			v2[k2][0]=max(v2[k2][0],k1);
			v3[k2][1]=min(v3[k2][1],k1-1);
		}
		if(k3==3)v3[k2][0]=max(v3[k2][0],k1);
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++)dp[i][j]=0;
		hsum[i]=lsum[i]=0;
		zz[i]=0;
	}
	dp[0][0]=3;
	hsum[0]=lsum[0]=3;
	q[lft=rgt=50000]=0;
	del(1);
	for(int i=2;i<=n;i++){
		for(int j=0;j<i-1;j++)stk[j]=(hsum[j]+lsum[j])%MOD;
		for(int j=0;j<i-1;j++)add(j,i-1,stk[j]);
		q[++rgt]=i-1;
		del(i);
	}
	ans=0;
	for(int i=0;i<=n;i++)ans=(ans+hsum[i])%MOD;
	ans%=MOD;
	ans+=MOD;
	ans%=MOD;
	cout<<ans<<endl;
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)sol();
	return 0;
}