#include<bits/stdc++.h>
using namespace std;


int n,m,A[10001],X[10001],B[10001],Y[10001];
bitset<66> b[66],e; int f[22];
long long ans;

inline int find(int x){return (x==f[x]?x:f[x]=find(f[x]));}

inline void ad(int x,int y){b[x][y]=b[y][x]=1;}

inline long long dfs(bitset<66> vis){

int cnt[22];
long long prod=1;
for (int i=0;i<n;++i) f[i]=i;
for (int i=0;i<n;++i) cnt[i]=3-vis[3*i]-vis[3*i+1]-vis[3*i+2];

int Niko=1;
for (int i=0;i<n;++i) if (cnt[i]) Niko=0;
if (Niko) return 1;

bitset<22> ttmp;
for (int i=0;i<n;++i) if (cnt[i]){
for (int j=i+1;j<n;++j) if (cnt[j]){
bitset<66> M;
if (!vis[i*3]) M|=b[i*3];
if (!vis[i*3+1]) M|=b[i*3+1];
if (!vis[i*3+2]) M|=b[i*3+2];
if (((!vis[j*3])&M[j*3]) || ((!vis[j*3+1])&M[j*3+1]) || ((!vis[j*3+2])&M[j*3+2]))
f[find(i)]=find(j),ttmp[i]=ttmp[j]=1;
}
}

for (int i=0;i<n;++i) if (cnt[i] && !ttmp[i]) prod*=cnt[i],cnt[i]=0,vis[3*i]=vis[3*i+1]=vis[3*i+2]=1;

int g=-1,C=0;
for (int i=0;i<n;++i) if (cnt[i]) g=i,++C;
if (g==-1){return prod;}

bitset<22> ing; 
for (int i=0;i<n;++i) if (cnt[i] && find(i)==find(g)) ing[i]=1;
if (ing.count()!=C){
auto previs=vis;
for (int j=0;j<n;++j) if (!ing[j]) vis[3*j]=vis[3*j+1]=vis[3*j+2]=1;
auto ways=dfs(vis);
vis=previs;
for (int j=0;j<n;++j) if (ing[j]) vis[3*j]=vis[3*j+1]=vis[3*j+2]=1;
return ways*prod*dfs(vis);
}

int tmp=0;

for (int i=0;i<n;++i) if (cnt[i]==1){
tmp=1;
int x=3*i; while (vis[x]) ++x;
for (int j=0;j<3*n;++j) if (b[x][j] && !vis[j]){
if (cnt[j/3]==1) return 0;
--cnt[j/3]; vis[j]=1;
}
vis[x]=1,cnt[i]=0;
}

if (tmp) return prod*dfs(vis);

int ma=-1,id=0;
for (int i=0;i<3*n;++i) if (!vis[i]){
int R=(b[i]&(~vis)).count();
if (R>ma) ma=R,id=i;
}

vis[id]=1; auto nowans=(cnt[id/3]==1?0:dfs(vis));
vis[id/3*3]=vis[id/3*3+1]=vis[id/3*3+2]=1;
for (int i=0;i<3*n;++i) if (!vis[i] && b[id][i]){
if (cnt[i/3]==1) return prod*nowans;
--cnt[i/3]; vis[i]=1;
}

return prod*(nowans+dfs(vis));

}

int main(){
ios::sync_with_stdio(false),cin.tie(0);

cin>>n>>m;
for (int i=1;i<=m;++i){
cin>>A[i]>>X[i]>>B[i]>>Y[i];
--A[i],--B[i];
ad(A[i]*3+X[i],B[i]*3+Y[i]);
}

for (int i=0;i<n;++i) ad(i*3,i*3+1),ad(i*3,i*3+2),ad(i*3+1,i*3+2);

ans=dfs(e);
cout<<ans<<'\n';

return 0;
}