//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=2.1e3+10;
int n,m,a[N],b[N],x[N],y[N];
ull an[25][3],val[25];map<ull,int>mp[25];
inline int dfs(int x,ull g){
	if (x<0) return 1;
	if (mp[x].count(g)) return mp[x][g];
	int sm=0;
	rep(i,0,2) if (x==n-1 || (!(g>>(x*3+i)&1)))
		sm+=dfs(x-1,(g&val[x])|an[x][i]);
	return mp[x][g]=sm;
}
inline void solve(){
	cin>>n>>m;
	if (n==1) return cout<<3<<'\n',void();
	rep(i,1,m){
		cin>>a[i]>>x[i]>>b[i]>>y[i],--a[i],--b[i];
		an[b[i]][y[i]]|=1ull<<(a[i]*3+x[i]);
	}
	rep(i,0,n-1) val[i]=(1ull<<(3*i))-1;
	cout<<dfs(n-1,0)<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
	// cin>>t;
	while (t--) solve();
	return 0;
}