// 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;
bool G[N][K];
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, buk[3] = {1, 1, 1};
			for(int i = 1; i <= 13; ++i) {
				int x = tmp % 3; tmp /= 3;
				if(!G[u][i]) continue;
				if(x == 1) buk[2] = 0;
				if(x == 2) buk[1] = 0;
				if(!buk[1] && !buk[2]) break;
			}
			for(int x : {0, 1, 2}) if(buk[x]) {
				int T = (S * 3 + x) % M;
				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;
}