#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 60,MAXM = 1.6e6,M = 13;
void add(int& x,int y){x=(x+y);}

int n,m,f[MAXN];

int dp[2][MAXM],s[MAXM][2],r[M],pw[M],U;

void dfs(int r,int id,int s0,int s1){
	if(r==M){
		s[id][0]=s0,s[id][1]=s1;
		return;
	}
	dfs(r+1,id,s0,s1);
	dfs(r+1,id+pw[r],s0|(1<<r),s1);
	dfs(r+1,id+2*pw[r],s0,s1|(1<<r));
}

int main(){
	pw[0]=1;rep(i,1,M-1)pw[i]=pw[i-1]*3;
	U=pw[M-1]*3;

	cin>>n>>m;
	rep(i,1,m){
		int u,v;cin>>u>>v;
		if(u>v)swap(u,v);
		f[v]|=(1<<(v-u-1));
	}

	dfs(0,0,0,0); //预处理

	dp[0][0]=1;
	rep(i,1,n){
		int t=i&1;
		rep(S,0,U-1)if(dp[t^1][S]){
			int& ret=dp[t^1][S],nS=S%pw[M-1]*3;
			//不选
			add(dp[t][nS],ret);
			//染颜色0
			if(!(f[i]&s[S][1])){
				add(dp[t][nS+1],ret);
			}
			//染颜色1
			if(!(f[i]&s[S][0])){
				add(dp[t][nS+2],ret);
			}
			ret=0;
		}
	}

	int ans=0;
	rep(S,0,U-1)add(ans,dp[n&1][S]);
	ans=(ans+3)%4;
	ans/=2;
	cout<<ans<<endl;
    return 0;
}