#define MOD 1000000007
#include<stdio.h>
typedef struct{
	long long arr[6][6];
}M;
int n,m;
int op[7];
void init(){
	op[1] = 4;
	op[4] = 1;
	op[2] = 5;
	op[5] = 2;
	op[3] = 6;
	op[6] = 3;
}
long long fun(long long a,long long n){
	long long r = 1;
	while(n > 0){
		if(n & 1)
			r = (r*a)%MOD;
		a =(a*a)%MOD;
		n = n>>1;
	}
	return r;
}
M j_z_xc(M m1,M m2){
	M ans;
	for(int i = 0;i < 6;i++){
		for(int k = 0;k < 6;k++){
			ans.arr[i][k] = 0;
			for(int j = 0;j < 6;j++){
				ans.arr[i][k] += m1.arr[i][j]*m2.arr[j][k]%MOD;
			}
		}
	}
	return ans;
}
M mpow(M m,int k){
	M ans;
	for(int i = 0;i < 6;i++){
		for(int j = 0;j < 6;j++){
			if(i == j){
				ans.arr[i][j] = 1;
			}else{
				ans.arr[i][j] = 0;
			}
		}
	}
	while(k > 0){
		if(k & 1){
			ans = j_z_xc(ans,m);
		}
		m = j_z_xc(m,m);
		k = k>>1;
	}
	return ans;
}
int main(){
	init();
	scanf("%d %d",&n,&m);
	M c_t;
	for(int i = 0;i < 6;i++){
		for(int j = 0;j < 6;j++){
			c_t.arr[i][j] = 1;
		}
	}
	for(int i = 0;i < m;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		c_t.arr[op[a]-1][b-1] = 0;
		c_t.arr[op[b]-1][a-1] = 0;
	}
	M c_t_n_1 = mpow(c_t,n-1);
	long long sum = 0;
	for(int i = 0;i < 6;i++){
		for(int j = 0;j < 6;j++){
			sum += c_t_n_1.arr[i][j]%MOD;
		}
	}
	long long num = fun(4,n);
	printf("%lli",sum*num%MOD);
	return 0;
}