#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]; int mp[65][1<<19]; inline int dfs(int sz,ll S){ if(sz<0)return 0; if(S<(1<<19)&&(~mp[sz][S]))return mp[sz][S]; if(!S)return !sz; if(sz>ppc(S))return 0; int p=__lg(S); int ans=(dfs(sz-1,S^(S&e[p])^(1ll<<p))*1llu*w[p]+dfs(sz,S^(1ll<<p)))%mod; if(S<(1<<19))mp[sz][S]=ans; return ans; } void slv(){ n=read(),k=read(); memset(mp,-1,sizeof(mp)); 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; int res=0; up(i,0,min(n,k))res=(res+dfs(i,(1ll<<k)-1)*1llu*jc[n-i])%mod; cout<<res; } int main(){ //freopen("matrix.in","r",stdin),freopen("matrix.out","w",stdout); slv(); return 0; }