#include<bits/stdc++.h> #include<bits/extc++.h> #define ll long long #define ppc __builtin_popcountll using namespace std; const int N=1e5+10,M=65,mod=1e9+7; void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;} vector<int> E[M]; int f[M][M],C[M][M],du[M],x[M],y[M],w[M]; int fac[N]; int n,k; //struct myhash{ll operator()(const ll &x)const{return x%mod;}}; //__gnu_pbds::gp_hash_table<ll,int,myhash> DP[M],vis; //unordered_map<ll,int> DP[M],vis; bool ok[M],vis[M];int dp[2][M][2],tmp[2][N][2]; vector<int> ms; void pdfs(int u,int st){ if(u==st){ dp[0][0][0]=1; dp[1][1][1]=w[u]; }else{ for(int o=0;o<=1;o++)for(int i=k;i>=0;i--){ Add(dp[o][i+1][1],1ll*dp[o][i][0]*w[u]%mod); Add(dp[o][i][0],dp[o][i][1]);dp[o][i][1]=0; } } vis[u]=1; for(auto v:E[u]){ if(vis[v]||!ok[v]) continue; pdfs(v,st); } } void calc(int dep,ll S){ f[dep][0]=1; for(int i=1;i<=k;i++) vis[i]=0,ok[i]=0; ms.clear(); for(int i=1;i<=k;i++){ if((S>>(i-1))&1) ms.push_back(i),ok[i]=1; } sort(ms.begin(),ms.end(),[&](int x,int y){return du[x]<du[y];}); for(auto ed:ms){ if(!vis[ed]){ if(du[ed]==0){ for(int j=ppc(S);j>=1;j--){ f[dep][j]=(f[dep][j]+1ll*f[dep][j-1]*w[ed])%mod; } }else{ memset(dp,0,sizeof(dp)); pdfs(ed,ed); /*for(int j=0;j<=ppc(S);j++){ cout<<dp[1][j][1]<<endl; }cout<<endl;*/ for(int j=ppc(S);j>=0;j--){ for(int x=1;j+x<=ppc(S);x++){ int val=0; if(du[ed]==1){ Add(val,dp[1][x][1]); }Add(val,dp[0][x][0]);Add(val,dp[1][x][0]);Add(val,dp[0][x][1]); Add(f[dep][j+x],1ll*val*f[dep][j]%mod); } } } } } //cout<<S<<endl; //for(int j=0;j<=ppc(S);j++) cout<<f[dep][j]<<' ';cout<<endl; //for(int i=1;i<=n;i++) cout<<du[i]<<' ';cout<<endl; } void dfs(int dep,ll S){ memset(f[dep],0,sizeof(f[dep])); /*if(ppc(S)<=20){ if(vis[S]){ for(int i=0;i<=ppc(S);i++) f[dep][i]=DP[i][S]; return ; }vis[S]=1; }*/ int mx=-1,mxid=0; for(int i=1;i<=k;i++){ if((S>>(i-1))&1){ if(du[i]>mx) mx=du[i],mxid=i; } } if(mx<=2){ calc(dep,S); /*return ; f[dep][0]=1; for(int i=1;i<=k;i++){ if((S>>(i-1))&1){ for(int j=ppc(S);j>=1;j--){ f[dep][j]=(f[dep][j]+1ll*f[dep][j-1]*w[i])%mod; } } }*/ //cout<<"1:"<<dep<<' '<<S<<endl; //for(int i=0;i<=ppc(S);i++) cout<<f[dep][i]<<' ';cout<<endl; /*for(int i=0;i<=ppc(S);i++){ f[dep][i]=C[ppc(S)][i]; }*/ }else{ vector<int> v1,v2; for(auto x:E[mxid]){ if((S>>(x-1))&1) v1.push_back(x); } for(auto ed:v1)for(auto x:E[ed]){ if((S>>(x-1))&1) v2.push_back(x); } ll ns=S^(1ll<<(mxid-1)); for(auto ed:v1) du[ed]--; dfs(dep+1,ns); for(auto ed:v1) du[ed]++,ns^=(1ll<<(ed-1)); for(int i=0;i<=ppc(S);i++) f[dep][i]=f[dep+1][i]; for(auto ed:v2) du[ed]--; dfs(dep+1,ns); //cout<<dep<<' '<<S<<endl; //for(int i=0;i<=ppc(S);i++) cout<<f[dep][i]<<' ';cout<<endl; for(auto ed:v2) du[ed]++; for(int i=1;i<=ppc(S);i++) f[dep][i]=(f[dep][i]+1ll*w[mxid]*f[dep+1][i-1])%mod; //cout<<dep<<' '<<S<<endl; //for(int i=0;i<=ppc(S);i++) cout<<f[dep][i]<<' ';cout<<endl; } //if(ppc(S)<=20) for(int i=0;i<=ppc(S);i++) DP[i][S]=f[dep][i]; } int main(){ //freopen("matrix.in","r",stdin); //freopen("matrix.out","w",stdout); cin>>n>>k; for(int i=1;i<=k;i++) cin>>x[i]>>y[i]>>w[i]; for(int i=1;i<=k;i++) w[i]--; C[0][0]=1; for(int i=1;i<=k;i++){ C[i][0]=1; for(int j=1;j<=i;j++){ C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } } fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod; for(int i=1;i<=k;i++){ for(int j=1;j<=k;j++){ if(i==j) continue; if(x[i]==x[j]||y[i]==y[j]){ E[i].push_back(j); } } }for(int i=1;i<=k;i++) du[i]=E[i].size(); ll U=(1ll<<k)-1; dfs(1,U); int ans=0; for(int i=1;i<=k;i++){ //cout<<i<<' '<<f[1][i]<<endl; ans=(ans+1ll*f[1][i]*fac[n-i])%mod; }Add(ans,fac[n]); cout<<ans<<endl; return 0; }