// They say that life is always easier
// After you let yourself come undone
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 55;
const int K = 13;
const int M = 1594323;
int n, m, G[N][K], pre[14];
short f[N][M];
int main() {
	//freopen("data.in", "r", stdin);
	//freopen("code.out", "w", stdout);
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;
		if(u > v) swap(u, v);
		G[v][v - u] = 1;
	}
	f[0][0] = 1;
	for(int u = 1; u <= n; ++u) 
		for(int S = 0; S < M; ++S) if(f[u - 1][S]) {
			int tmp = S;
			for(int i = 1; i <= 13; ++i)
				pre[i] = tmp % 3, tmp /= 3;
			for(int x : {0, 1, 2}) {
				pre[0] = x;
				bool isOK = 1;
				if(x) for(int i = 1; i <= 13; ++i)
					if(G[u][i - 1] && pre[i] && x != pre[i]) isOK = 0;
				if(!isOK) continue;
				int T = 0, now = 1;
				for(int i = 0; i < 13; ++i)
					T += pre[i] * now, now *= 3;
				f[u][T] = (f[u][T] + f[u - 1][S]) & 3;
			}
		}
	short ans = 0;
	for(int S = 0; S < M; ++S)
		ans = (ans + f[n][S]) & 3;
	printf("%d\n", ans / 2);
	return 0;
}