此份代码能在 newoj中AC

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <cmath>

#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
ll n, m;
struct Matrix {
    ll v[6][6];
};

ll QuickPow(ll x, ll N) {
    ll res = x;
    ll ans = 1;
    while (N) {
        if (N & 1) {
            ans = ans * res % mod;
        }
        res = res * res % mod;
        N = N >> 1;
    }
    return ans % mod;
}

Matrix mul(Matrix a, Matrix b, int rank) {
    Matrix tmp;
    memset(tmp.v, 0, sizeof(tmp.v));
    for (int i = 0; i < rank; i++) {
        for (int j = 0; j < rank; j++) {
            for (int k = 0; k < rank; k++) {
                tmp.v[i][j] = (tmp.v[i][j] + a.v[i][k] * b.v[k][j] % mod) % mod;
            }
        }
    }
    return tmp;
}

Matrix QuickPower(Matrix res, ll N, int rank) {
    Matrix ans;
    for (int i = 0; i < rank; i++) {
        for (int j = 0; j < rank; j++) {
            ans.v[i][j] = (i == j);
        }
    }
    while (N) {
        if (N & 1) {
            ans = mul(ans, res, rank);
        }
        res = mul(res, res, rank);
        N = N >> 1;
    }
    return ans;
}

int main() {
    while (cin >> n >> m) {
        Matrix res, ans;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                res.v[i][j] = 1;
            }
        }
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            res.v[a][(b + 3) % 6] = res.v[b][(a + 3) % 6] = 0;
        }
        ans = QuickPower(res, n - 1, 6);
        ll a1 = QuickPow(4, n);
        ll sum = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                sum = (sum + ans.v[i][j]) % mod;
            }
        }
        cout << (sum * a1) % mod << endl;
    }
    return 0;
}