#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5e3+3;
const ll mod = 1e9+7;

int n,m,yl[N],yr[N];
ll sx[N],sy[N],dp[N][N];
int mn[N][4],mx[N][4];

void upd(int y,int l,int r){
	if (yl[y]<yr[y]){
		l=max(l,yl[y]),r=min(r,yr[y]);
		if (l<=r){
			for (int x=yl[y]; x<l; x++){
				sx[x]=(sx[x]-dp[y][x]+mod)%mod;
				sy[y]=(sy[y]-dp[y][x]+mod)%mod;
			}
			for (int x=r+1; x<=yr[y]; x++){
				sx[x]=(sx[x]-dp[y][x]+mod)%mod;
				sy[y]=(sy[y]-dp[y][x]+mod)%mod;
			}
		}
		else{
			for (int x=yl[y]; x<=yr[y]; x++){
				sx[x]=(sx[x]-dp[y][x]+mod)%mod;
				sy[y]=(sy[y]-dp[y][x]+mod)%mod;
			}
		}
	}
	yl[y]=l,yr[y]=r;
}

void solve(){
	cin>>n>>m;
	for (int i=0; i<=n; i++){
		yl[i]=0,yr[i]=i,sx[i]=sy[i]=0;
		for (int j=0; j<4; j++)
			mn[i][j]=i,mx[i][j]=0;
		for (int j=0; j<=n; j++)
			dp[i][j]=0;
	}
	for (int i=1; i<=m; i++){
		int l,r,x;
		cin>>l>>r>>x;
		mn[r][x]=min(mn[r][x],l);
		mx[r][x]=max(mx[r][x],l);
	}
	dp[0][0]=3,sx[0]=sy[0]=3;
	ll ans=0;
	for (int i=1; i<=n; i++){
		int x_l=mx[i][3],x_r=mn[i][2],y_l=mx[i][2],y_r=mn[i][1];
		for (int y=0; y<y_l; y++){
			upd(y,i,i);
		}
		for (int y=y_l; y<y_r; y++){
			upd(y,x_l,x_r-1);
		}
		for (int y=y_r; y<i; y++){
			upd(y,i,i);
		}
		if (i==n){
			for (int x=x_l; x<x_r; x++){
				ans=(ans+sx[x])%mod;
			}
			break;
		}
		for (int y=y_l; y<y_r; y++){
			dp[i][y]=(dp[i][y]+sy[y])%mod;
		}
		for (int x=x_l; x<x_r; x++){
			dp[i][x]=(dp[i][x]+sx[x])%mod;
		}
		for (int j=0; j<=i; j++){
			sx[j]=(sx[j]+dp[i][j])%mod;
			sy[i]=(sy[i]+dp[i][j])%mod;
		}
	}
	cout<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin>>t;
	while (t--){
		solve();
	}
	return 0;
}

// TRY! TRY! TRY!

/*
Think twice before coding. Have you overkilled?
Think twice before submitting.
Check on the samples and constraints carefully.
*/

/*
Be brave to guess.
Is your former/first approach correct?
Follow your intuition.
Use a notebook to note down your ideas and check whether they are correct.
*/

/*
A simple brute force may work? There is some limit on the answer?
Try to find patterns.
*/