/*
[templates]: 
duipai
spjdp
compre
addhis
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0)); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍！
//use std::array.
const int mod = 1e9 + 7; 
struct con {
    int jl, jr; int kl, kr;
    con() {}
    con(int x) {jl = 0; jr = x; kl = 0; kr = x; } 
    con(int _jl, int _jr, int _kl, int _kr):jl(_jl),jr(_jr),kl(_kl),kr(_kr){}
};
con merge(con th, con op) {
    return con(max(th.jl, op.jl), min(th.jr, op.jr), max(th.kl, op.kl), min(th.kr, op.kr)); 
}
con calc(int x, int y, int z) {
    if(z == 1) return con(0, x - 1, 0, x - 1);
    else if(z == 2) return con(x, y - 1, 0, x - 1); 
    else return con(x, y - 1, x, y - 1); 
}
con v[5050]; 
bool emp(con x) {return (x.jr < x.jl || x.kr < x.kl); }
bool buhan(int x, int y, int z) {return z < x || z > y; }
deque<int> hang[5050], lie[5050]; int shang[5050], slie[5050]; int dp[5050][5050]; 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int T; cin >> T;
    while(T--) {
        int n, m; cin >> n >> m;
        f(i, 1, n) v[i] = con(i); 
        f(i, 0, n - 1) f(j, 0, n - 1) dp[i][j] = 0;
        f(i, 0, n - 1) slie[i] = shang[i] = 0; 
        f(i, 0, n - 1) { lie[i].clear(); hang[i].clear(); }
        f(i, 1, m) {
            int x, y, z; cin >> x >> y >> z; 
            v[y] = merge(v[y], calc(x, y, z)); 
        }
     //   f(i, 1, n) cerr << v[i].jl << " " << v[i].jr<<" "<<v[i].kl<<" "<<v[i].kr<<endl;
     //   cerr << endl; 
        if(emp(v[1])) {cout << 0 << endl; continue; }
        else {shang[0] = slie[0] = dp[0][0] = 3; hang[0].push_back(0); lie[0].push_back(0); }
        f(i, 1, n) {
            if(i != 1) {
                f(j, 0, i - 2) {
                    //dp_{i-1,j} = hang_j + lie_j
                    dp[i-1][j] = shang[j] + slie[j]; dp[i-1][j] %= mod; 
                    shang[i-1] += shang[j] + slie[j]; shang[i-1] %= mod; 
                    slie[j] += shang[j] + slie[j]; slie[j] %= mod; 
                    hang[i-1].push_back(j); lie[j].push_back(i-1); 
                }
            }
            f(j, 0, i - 1) {
                if(buhan(v[i].jl, v[i].jr, j)) {
                    shang[j] = 0; hang[j].clear();  
                }
                else {
                    while(!hang[j].empty() && buhan(v[i].kl, v[i].kr, hang[j].front())) {
                        shang[j] = shang[j] + mod - dp[j][hang[j].front()]; 
                        shang[j] %= mod; hang[j].pop_front(); 
                    }
                    while(!hang[j].empty() && buhan(v[i].kl, v[i].kr, hang[j].back())) {
                        shang[j] = shang[j] + mod - dp[j][hang[j].back()]; 
                        shang[j] %= mod; hang[j].pop_back(); 
                    }
                }
            }
            f(j, 0, i - 1) {
                if(buhan(v[i].kl, v[i].kr, j)) {
                    slie[j] = 0; lie[j].clear();  
                }
                else {
                    while(!lie[j].empty() && buhan(v[i].jl, v[i].jr, lie[j].front())) {
                        slie[j] = slie[j] + mod - dp[lie[j].front()][j]; 
                        slie[j] %= mod; lie[j].pop_front(); 
                    }
                    while(!lie[j].empty() && buhan(v[i].jl, v[i].jr, lie[j].back())) {
                        slie[j] = slie[j] + mod - dp[lie[j].back()][j]; 
                        slie[j] %= mod; lie[j].pop_back(); 
                    }
                }
            }
            
         //   f(x, 0, i - 1) f(y, 0, i - 1) cout << dp[x][y] << " \n"[y == i - 1]; 
        }
        int ans = 0; 
        f(i, 0, n - 1)  {ans = (ans + slie[i]) % mod;}
        cout << ans << endl; 
    }
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}