#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const int N=5005,mod=1000000007;
struct Matrix {
    int l1,r1,l2,r2;
    inline Matrix operator*(const Matrix o) {
        return {max(l1,o.l1),min(r1,o.r1),max(l2,o.l2),min(r2,o.r2)};
    }
}mat[N];
int n,m;
int Lj,Lk[N],Rk[N];
int Sj[N],Sk[N],f[N][N];
inline void solve() {
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) mat[i]={0,n,0,n};
    while (m--) {
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        Matrix x;
        if (c==1) x={0,l-1,0,l-1};
        else if (c==2) x={l,n,0,l-1};
        else x={l+1,n,l,n};
        mat[r]=mat[r]*x;
    }
    // for (int i=1;i<=n;i++) {
    //     printf("%d %d %d %d\n",mat[i].l1,mat[i].r1,mat[i].l2,mat[i].r2);
    // }
    if (mat[1].l1!=0) {
        puts("0");
        return;
    }
    Lj=0;
    for (int i=0;i<=n;i++) Lk[i]=0,Rk[i]=n;
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) f[i][i]=0;
    for (int i=0;i<=n;i++) Sj[i]=Sk[i]=0;
    f[0][0]=Sj[0]=Sk[0]=3;
    for (int i=1;i<n;i++) {
        for (int k=0;k<i;k++) {
            int d=(Sj[k]+Sk[k])%mod;
            f[i][k]=d,Sk[k]=(Sk[k]+d)%mod,Sj[i]=(Sj[i]+d)%mod;
        }
        for (int j=0;j<mat[i+1].l1&&j<=i;j++) {
            Sj[j]=0;
            for (int k=Lk[j];k<=Rk[j];k++) {
                Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
                f[j][k]=0;
            }
            Lk[j]=n,Rk[j]=0;
        }
        for (int j=mat[i+1].r1+1;j<=i;j++) {
            Sj[j]=0;
            for (int k=Lk[j];k<=Rk[j];k++) {
                Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
                f[j][k]=0;
            }
            Lk[j]=n,Rk[j]=0;
        }
        for (int j=mat[i+1].l1;j<=i&&j<=mat[i+1].r1;j++) {
            int L=max(Lk[j],mat[i+1].l2);
            int R=min(Rk[j],mat[i+1].r2);
            if (L>R) {
                Sj[j]=0;
                for (int k=Lk[j];k<=Rk[j];k++) {
                    Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
                    f[j][k]=0;
                }
                Lk[j]=n,Rk[j]=0;
            } else {
                for (int k=Lk[j];k<L;k++) Sj[j]=(Sj[j]-f[j][k]+mod)%mod,Sk[k]=(Sk[k]-f[j][k]+mod)%mod,f[j][k]=0;
                for (int k=R+1;k<=Rk[j];k++) Sj[j]=(Sj[j]-f[j][k]+mod)%mod,Sk[k]=(Sk[k]-f[j][k]+mod)%mod,f[j][k]=0;
                Lk[j]=L,Rk[j]=R;
            }
        }
    }
    // for (int i=0;i<=n;i++) {
    //     for (int j=0;j<=n;j++) {
    //         printf("%d ",f[i][j]);
    //     }
    //     puts("");
    // }
    int ans=0;
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) ans=(ans+f[i][j])%mod;
    printf("%d\n",ans);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
    freopen("err", "w", stderr);
#endif
    int T;
    scanf("%d",&T);
    while (T--) solve();
    return 0;
}