#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcountll using namespace std; typedef long long ll; typedef long double db; const int maxn=1e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,k,jc[maxn],a[65],b[65],w[65],vis1[maxn],vis2[maxn]; ll e[55]; unordered_map<ll,int>mp[65]; inline int dfs(int sz,ll S){ if(sz<0)return 0; if(mp[sz].count(S))return mp[sz][S]; if(!S)return !sz; if(sz>ppc(S))return 0; int p=__lg(S); return mp[sz][S]=(dfs(sz-1,S^(S&e[p])^(1ll<<p))*1llu*w[p]+dfs(sz,S^(1ll<<p)))%mod; } int A[70],B[70]; void slv(){ n=read(),k=read(); jc[0]=1;up(i,1,n)jc[i]=jc[i-1]*1llu*i%mod; up(i,0,k-1)a[i]=read(),b[i]=read(),w[i]=read()-1; up(i,0,k-1) up(j,i+1,k-1)if(a[i]==a[j]||b[i]==b[j])e[i]|=1ll<<j,e[j]|=1ll<<i; A[0]=1; ll S=(1ll<<k)-1; up(i,0,k-1)if(!e[i]){ up(j,0,k){ B[j]=A[j]; if(j)B[j]=(B[j]+A[j-1]*1llu*w[i])%mod; }up(j,0,k)A[j]=B[j]; S^=1ll<<i; } up(i,0,k)B[i]=dfs(i,S);int res=0; up(i,0,k) up(j,0,k-i) if(i+j<=n)res=(res+A[i]*1llu*B[j]%mod*1llu*jc[n-i-j])%mod; cout<<res; } int main(){ //freopen("matrix.in","r",stdin),freopen("matrix.out","w",stdout); slv(); return 0; }