#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
#define isz(v) (int)(v.size())
using namespace std;

const int maxn=55; 
const int maxs=1600005;
const int lim=12;
const int inf=0x3f3f3f3f;
const int p13=531441;

namespace Solve {
	int pw[maxn];
	bool e[maxn][maxn];
	int cur;
	int f[maxs];
	int g[maxs];
	void clear() {
		memset(e,0,sizeof(e));
	}
	void add(int &x,int y) {
		x=(x+y)&3;
	}
	void dfs(int x,int s) {
		if(!x) {
			bool p=true,q=true;
			int t=s,now=0;
			while(t) {
				++now;
				if(t%3==0&&e[cur][now]) {
					q=false;
				} else if(t%3==1&&e[cur][now]) {
					p=false;
				}
				t/=3;
			}
			if(p) {
				add(g[(s*3)%p13+0],f[s]);
			}
			if(q) {
				add(g[(s*3)%p13+1],f[s]);
			}
			add(g[(s*3)%p13+2],f[s]);
			return ;
		}
		dfs(x-1,s*3+0);
		dfs(x-1,s*3+1);
		dfs(x-1,s*3+2);
	}
	void main(int tid) {
		int n,m;
		cin>>n>>m;
		pw[0]=1;
		for(int i=1;i<=lim;i++) {
			pw[i]=3*pw[i-1];
		}
		for(int i=1;i<=m;i++) {
			int x,y;
			cin>>x>>y;
			if(x>y) {
				swap(x,y);
			}
			e[y][y-x]=true;
		}
		memset(f,0,sizeof(f));
		f[p13-1]=1;
		for(cur=1;cur<=n;cur++) {
			memset(g,0,sizeof(g));
			dfs(lim,0);
			memcpy(f,g,sizeof(f));
		}
		int ans=0;
		for(int s=0;s<=p13-1;s++) {
			add(ans,f[s]);
		}
		cout<<(ans>>1)<<"\n";
	}
	void init() {
		
	}
}

signed main() {
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	Solve::init();
	for(int t=1;t<=T;t++) {
		Solve::main(t);
		Solve::clear();
	}
#ifndef ONLINE_JUDGE
	cerr<<"Time: "<<clock()<<"ms\n";
#endif
}