#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ull unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=5005;
const int mod=1e9+7;
int T,n,m;
int f[N][N],a[N],b[N],c[N],d,a0[N],b0[N],c0[N],d0,pl[N],pr[N];
vector<pair<int,int>>q[N];
void add(int i,int j,int x){
    f[i][j]=(f[i][j]+x)%mod;
    a0[i]=(a0[i]+x)%mod;
    b0[j]=(b0[j]+x)%mod;
}
void del(int i,int j){
    int x=f[i][j];
    a0[i]=(a0[i]-x)%mod;
    b0[j]=(b0[j]-x)%mod;
    f[i][j]=0;
}
void sol(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)a[i]=b[i]=c[i]=0,q[i].clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=0;
        }
    }
    d=1;
    for(int i=1;i<=m;i++){
        int l,r,x;
        cin>>l>>r>>x;
        q[r].pb({l,x});
    }
    for(int i=1;i<=n;i++)pl[i]=1,pr[i]=i;
    int f1=1,f2=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i-1;j++)a0[j]=a[j],b0[j]=b[j],c0[j]=c[j];
        d0=0;
        for(int j=1;j<=i-2;j++){
            add(i-1,j,a[j]);
            add(i-1,j,b[j]);
            c0[i-1]=(c0[i-1]+c[j])%mod;
            add(i-1,j,c[j]);
        }
        c0[i-1]+=d;
        int l1=1,r1=i-1,l2=1,r2=i-1;
        for(auto j:q[i]){
            if(j.se==1){
                r1=min(r1,j.fi-1);
            }
            else if(j.se==2){
                f1=0;
                l2=max(l2,j.fi);
                r1=min(r1,j.fi-1);
            }
            else{
                f1=f2=0;
                l1=max(l1,j.fi);
            }
        }
        if(!f2){
            for(int j=1;j<=i-1;j++)c0[j]=0;
        }
        else{
            for(int j=r1+1;j<=i-1;j++)c0[j]=0;
        }
        if(f1)d0=1;
        if(l1>r1||l2>r2)l1=i,r1=i-1;
        for(int j=1;j<l1;j++){
            for(int k=pl[j];k<=pr[j];j++)del(j,k);
            pl[j]=1,pr[j]=0;
        }
        for(int j=l1;j<=r1;j++){
            if(max(pl[j],l2)>min(pr[j],r2)){
                for(int k=pl[j];k<=pr[j];j++)del(j,k);
                pl[j]=1,pr[j]=0;
            }
            else{
                while(pl[j]<l2)del(j,pl[j]),pl[j]++;
                while(pr[j]>r2)del(j,pr[j]),pr[j]--;
            }
        }
        for(int j=r1+1;j<=i-1;j++){
            for(int k=pl[j];k<=pr[j];k++)del(j,k);
            pl[j]=1,pr[j]=0;
        }
        for(int j=1;j<=i-1;j++)a[j]=a0[j],b[j]=b0[j],c[j]=c0[j];
        d=d0;
    }
    int res=d*3;
    for(int i=1;i<n;i++)res=(res+1ll*a[i]*6)%mod;
    for(int i=1;i<n;i++)res=(res+1ll*c[i]*6)%mod;
    cout<<(res+mod)%mod<<"\n";
}
int main(){
    //freopen("data.in","r",stdin);
    // freopen("own.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        sol();
    }
}