#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 22,M = 10000;
int n,m,a[M + 5],b[M + 5],c[M + 5],d[M + 5],p[N + 5],flag[N + 5][3];
vector <pair <int,int> > v[N + 5][3];
ll dfs(int x)
{
	if(x == n + 1)return 1;
	int cnt = 0;ll res = 0;
	for(int i = 0;i < 3;i++)
	{
		p[x] = i;
		if(flag[x][i])continue;
		if(!v[x][i].size())cnt++;
		else
		{
			for(auto now : v[x][i])
				flag[now.first][now.second]++;
			res += dfs(x + 1);
			for(auto now : v[x][i])
				flag[now.first][now.second]--;
		}
	}
	if(cnt)p[x] = -1,res += cnt * dfs(x + 1);
	return res;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= m;i++)
		scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]),
		v[a[i]][b[i]].push_back({c[i],d[i]}); 
	cout<<dfs(1);
}