C++ :

#include <iostream>
#include <cstring>
#define MAX 6
#define MOD 1000000007
#define ll long long
using namespace std;
int reverse[6]={3,4,5,0,1,2};
struct matrix
{
	int n;
	ll d[MAX][MAX];
	matrix(){memset(d, 0, sizeof(d));}
};
matrix operator *(const matrix &m1, const matrix &m2)
{
	matrix res;
	res.n = m1.n;
	for(int i = 0; i < m1.n; i++)
		for(int j = 0; j < m1.n; j++)
			for(int k = 0; k < m1.n; k++)
			{
				res.d[i][j] += m1.d[i][k] * m2.d[k][j];
				res.d[i][j] %= MOD;
			}
	return res;
}
matrix operator ^(const matrix &m, ll n)
{
	matrix res;
	res.n = m.n;
	for(int i = 0; i < res.n; i++)
		res.d[i][i] = 1;
	matrix tmp = m;
	while(n)
	{
		if(n & 1)
			res = res * tmp;
		tmp = tmp * tmp;
		n >>= 1;
	}
	return res;
}
ll pow(ll n, ll m)
{
	ll ans = 1;
	while(m)
	{
		if(m & 1)
			ans = (ans * n) % MOD;
		m >>= 1;
		n = (n * n) % MOD;
	}
	return ans;
}
int main()
{
	int n, m, a, b;
	while(cin >> n >> m)
	{
		matrix mat;
		mat.n = 6;
		for(int i = 0; i < 6; i++)
			for(int j = 0; j < 6; j++)
				mat.d[i][j] = 1;
		for(int i = 0; i < m; i++)
		{
			cin >> a >> b;
			a--;b--;
			mat.d[a][reverse[b]]=mat.d[b][reverse[a]]=0;
		}
		mat = mat ^ (n - 1);
		ll ans = 0;
		for(int i = 0; i < 6; i++)
			for(int j = 0; j < 6; j++)
				ans = (ans + mat.d[i][j]) % MOD;
		cout << (ans * pow(4, n)) % MOD  << endl;
	}
	return 0;
}