#include<bits/stdc++.h>
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=5005,mod=1e9+7;
int T,n,m,f[N][N<<2],p[N][5][2];
bool tag[N][N<<2];
void build(int x,int p,int l,int r){
	f[x][p]=tag[x][p]=0;
	if(l==r) return;
	int mid=l+r>>1;
	build(x,ls,l,mid),build(x,rs,mid+1,r);
}
void pushdown(int x,int p,int l,int r){
	int mid=l+r>>1;
	if(tag[x][p]){
		tag[x][ls]=tag[x][rs]=1,f[x][ls]=f[x][rs]=0;
		tag[x][p]=0;
	}
}
void update(int x,int p,int l,int r,int ql,int qr){
	if(!f[x][p]) return;
	if(ql<=l&&r<=qr){
		f[x][p]=0;
		tag[x][p]=1;
		return;
	}
	pushdown(x,p,l,r);
	int mid=l+r>>1;
	if(ql<=mid) update(x,ls,l,mid,ql,qr);
	if(mid<qr) update(x,rs,mid+1,r,ql,qr);
	f[x][p]=(f[x][ls]+f[x][rs])%mod;
}
void add(int x,int p,int l,int r,int pos,int w){
	if(!w) return;
	f[x][p]=(f[x][p]+w)%mod;
	if(l==r) return;
	pushdown(x,p,l,r);
	int mid=l+r>>1;
	if(pos<=mid) add(x,ls,l,mid,pos,w);
	else add(x,rs,mid+1,r,pos,w);
}
void init(int r){
	for(int i=0;i<r;++i){
		int L=-1,R=n;
		if(~p[r][1][0]){
			if(i>=p[r][1][0]){
				update(i,1,0,n-1,0,n-1);
				continue;
			} else R=min(R,p[r][1][0]);
		}
		if(~p[r][3][1]){
			if(i>=p[r][3][1]) L=max(L,p[r][3][1]-1);
			else{
				update(i,1,0,n-1,0,n-1);
				continue;
			}
		}
		if(~p[r][2][0]){
			if(i>=p[r][2][0]) R=min(R,p[r][2][0]);
			else L=max(L,p[r][2][0]-1);
		}
		if(~p[r][2][1]){
			if(i>=p[r][2][1]) R=min(R,p[r][2][1]);
			else L=max(L,p[r][2][1]-1);
		}
		if(L>=R) update(i,1,0,n-1,0,n-1);
		else{
			if(L!=-1) update(i,1,0,n-1,0,L);
			if(R!=n) update(i,1,0,n-1,R,n-1);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;++i) memset(p[i],-1,sizeof(p[i]));
		while(m--){
			int l,r,x;
			cin>>l>>r>>x;
			if(p[r][x][0]==-1) p[r][x][0]=p[r][x][1]=l;
			else p[r][x][0]=min(p[r][x][0],l),p[r][x][1]=max(p[r][x][1],l);
		}
		for(int i=0;i<n;++i) build(i,1,0,n-1);
		add(0,1,0,n-1,0,1),init(1);
		for(int i=2;i<=n;++i){
			for(int j=0;j<i-1;++j){
				add(i-1,1,0,n-1,j,f[j][1]);
				add(j,1,0,n-1,i-1,f[j][1]);
			}
			init(i);
		}
		int ans=0;
		for(int i=0;i<n;++i) ans=(ans+f[i][1])%mod;
		cout<<3ll*ans%mod<<endl;
	}
	return 0;
}