#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn=1e5+;

const int MOD=;

LL a[maxn],b[maxn];

LL quick_pow(LL a,LL b)

{

    LL ans=;

    while(b)

    {

        if(b&)ans=ans*a%MOD;

        a=a*a%MOD;

        b>>=;

    }

    return ans%MOD;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        memset(a,,sizeof(a));

        memset(b,,sizeof(b));

        while(m--)

        {

            int x,y,c;

            scanf("%d%d%d",&x,&y,&c);

            if(c==)

            {

                a[x]++;

                a[y+]--;

            }

            else

            {

                b[x]++;

                b[y+]--;

            }

        }

        LL min1=a[],min2=b[];

        for(int i=;i<=n;i++)

        {

            a[i]+=a[i-];

            b[i]+=b[i-];

            min1=min(min1,a[i]);

            min2=min(min2,b[i]);

        }

        LL sum=quick_pow(,min1)%MOD*quick_pow(,min2)%MOD;

        printf("%lld\n",sum);

    }

    return ;

}