#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 22;
	LL n, m, rs, x, y, c1, c2, c[N], f[1 << N];
	vector<pii> g[N][3];
	int main() {
		cin >> n >> m;
		REP(i, 1, m) {
			cin >> x >> c1 >> y >> c2, x --, y --;
			g[x][c1].pb(y, c2), g[y][c2].pb(x, c1);
		}
		f[0] = 1;
		REP(S, 1, (1 << n) - 1) {
			int x = __lg(S & -S);
			for (int v : {0, 1}) {
				int T = 0, chk = 1;
				REP(i, 0, n - 1) c[i] = -1;
				queue<int> q; c[x] = v, q.push(x); 
				while (q.size()) {
					int u = q.front(); q.pop(), T |= 1 << u;
					for (auto [v, w] : g[u][c[u]]) {
						if (w == 2 || !(S >> v & 1)) continue;
						if (c[v] == -1) c[v] = !w, q.push(v);
						else chk &= (c[v] != w);
					}
				}
				if (chk) f[S] += f[S ^ T];
			}
		}
		REP(S, 0, (1 << n) - 1) {
			int chk = 1, T = (1 << n) - 1; queue<int> q;
			REP(i, 0, n - 1) {
				c[i] = -1;
				if (S >> i & 1) c[i] = 2, q.push(i);
			}
			while (q.size()) {
				int u = q.front(); q.pop(), T ^= 1 << u;
				for (auto [v, w] : g[u][c[u]]) {
					if (w == 2) { chk &= (c[v] != 2); continue; }
					if (c[v] == -1) c[v] = !w, q.push(v);
					else chk &= (c[v] != w);
				}
			}
			if (chk) rs += f[T];
		}
		cout << rs << '\n';
		return 0;
	}
}
int main() {
	// freopen("paint.in", "r", stdin);
	// freopen("paint.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
	while (T --) Milkcat::main();
	return 0;
}