/*
 * @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);
}