// clang-format off
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
mt19937 gen(time(0));
typedef long long ll; 
typedef unsigned long long ull; 
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; typedef pair<int,ll> pil;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int mod=1e9+7;
inline void plust(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void minut(int &x,int y){x=x-y<0?x-y+mod:x-y;}
const int N=5001;
// clang-format on
int n,m;
vector<pii>vec[N];
int a[N][N],b[N],c[N],l[N][N],u[N][N],r[N][N],d[N][N];
bool vis[N][N];
inline void add(int i,int j,int k){
	//assert(!vis[i][j] || !k);
	plust(a[i][j],k);
	plust(b[i],k); plust(c[j],k);
}
inline void del(int i,int j){
	assert(!vis[i][j]);vis[i][j]=1;
	int x=a[i][j];a[i][j]=0;
	minut(b[i],x),minut(c[j],x);
	int p=d[i][j],q=u[i][j];
	u[p][j]=q;
	if(~q)d[q][j]=p;
	p=l[i][j],q=r[i][j];
	l[i][q]=p;
	if(~p)r[i][p]=q;
}
int ans;
inline void solve(){
	n=read(),m=read();
	bool fl=0;
	rep(i,1,m){
		int l=read(),r=read(),x=read();
		if(l==1 && r==1 && x>1)fl=1;
		vec[r].pb(P(l,x));
	}
	if(fl){
		printf("0\n");
		goto clear;
	}
	rep(i,0,n)rep(j,0,n)l[i][j]=j-1,u[i][j]=i-1;
	rep(i,0,n)rep(j,0,n)r[i][j]=j+1,d[i][j]=i+1;
	add(0,0,1);
	rep(i,2,n){
		static int tb[N],tc[N];
		rep(j,0,i-1)tb[j]=b[j],tc[j]=c[j];
		rep(k,0,i-1)add(i-1,k,tc[k]);
		rep(j,0,i-1)add(i-1,j,tb[j]);
		for(auto tmp:vec[i]){
			int lim=tmp.fi,x=tmp.se;
			if(x==1){
				rep(j,lim,i-1)for(int k=l[j][i];~k;k=l[j][i])del(j,k);
			}
			if(x==2){
				rep(j,0,lim-1)for(int k=l[j][i];~k;k=l[j][k])del(j,k);
				rep(k,lim,i-1)for(int j=u[i][k];~j;j=u[j][k])del(j,k);
			}
			if(x==3){
				rep(k,0,lim-1)for(int j=u[i][k];~j;j=u[j][k])del(j,k);
			}
		}
	}
	ans=0;
	rep(j,0,n-1)plust(ans,3ll*b[j]%mod);
	printf("%d\n",ans);


clear:


	rep(i,0,n)rep(j,0,n)a[i][j]=l[i][j]=u[i][j]=r[i][j]=d[i][j]=0;
	rep(i,0,n)b[i]=c[i]=0;
	rep(i,1,n)vec[i].clear();
}
int main() {
    //freopen("data.in", "r", stdin);
    // freopen(".in","r",stdin);
    // freopen("myans.out","w",stdout);
	int T=read();while(T--)solve();
    return 0;
}