/*
* @Author: your name
* @Date: 2020-11-10 00:08:12
* @LastEditTime: 2020-11-12 19:43:46
* @LastEditors: wangziyang
* @Description: In User Settings Edit
* @FilePath: /algorithm/049-垒骰子.cpp
*/
/**
* *注意理解题面:“两种垒骰子方式相同:当且仅当这两种方式中对应高度的骰子的对应数字的 朝向 都相同。”。这意味着一个合法的骰子可以旋转4次变成4种情况
* */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000000010, MOD = 1000000000 + 7, K = 6;
int n, m;
int getOp(int x) {
if (x >= 3) return x - 3;// 注意我们假设骰子的数字是0~5
else return x + 3;
}
void mult(int c[][K], int a[][K], int b[][K]) {
int temp[K][K];
memset(temp, 0, sizeof temp); // 必须对局部数组进行初始化,否则你根本不知道数组的初始值是多少。
for (int i = 0; i < K; ++i) {
for (int j = 0; j < K; ++j) {
for (int t = 0; t < K; ++t) {
temp[i][j] = (temp[i][j] + (LL)a[i][t] * b[t][j]) % MOD;
}
}
}
memcpy(c, temp, sizeof temp);
}
int main()
{
scanf("%d%d", &n, &m);
int a[K][K];
for (int i = 0; i < 6; ++i) {
for (int j = 0; j < 6; ++j) {
a[i][j] = 4;
}
}
int x, y;
while(m--) {
scanf("%d%d", &x, &y); // 注意我们假设骰子的数字是0~5
x--;
y--;
a[x][getOp(y)] = 0;
a[y][getOp(x)] = 0;
}
int fn[K][K] = { //完全可以使用 1*6 矩阵,之所以使用 6*6 是因为这样可以少自定义一个矩阵1*6 与 矩阵6*6的乘法函数
{4, 4, 4, 4, 4, 4} // 初始化 f[0][0~5]。当只有一个骰子的时候,每种数字朝上的情况都是4种
};
n--; // 因为快速幂一共需要循环 n - 1 次
while (n) {
if (n & 1 == 1) {
mult(fn, fn, a);
}
n >>= 1;
mult(a, a, a);
}
int ans = 0;
for (int i = 0; i < K; ++i) {
ans = (ans + fn[0][i]) % MOD;
}
printf("%d\n", ans);
}