矩阵不会还麻烦还难（对我来说），不过dfs和dp都会过70%数据，供参考

dp+快速幂

#include <iostream>

using namespace std;

typedef long long LL;

const int MOD = 1e9 + 7;

int n, m;
int con[10][10]; // 冲突
int op[10]; // 对面
int f[2][10];

void init() {
    op[1] = 4, op[4] = 1;
    op[2] = 5, op[5] = 2;
    op[3] = 6, op[6] = 3;
}

int main(void) {
    init();
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        con[a][b] = true;
        con[b][a] = true;
    }

    for (int i = 1; i <= 6; ++i) f[0][i] = 1;

    int cur = 0;
    for (int le = 2; le <= n; ++le) { // 层数
        cur = 1 - cur;
        for (int j = 1; j <= 6; ++j) {
            f[cur][j] = 0;
            for (int i = 1; i <= 6; ++i) {
                int t = op[j];
                if (con[t][i]) continue;
                f[cur][j] = (f[cur][j] + f[1 - cur][i]) % MOD;
            }
        }
    }

    LL sum = 0;
    for (int i = 1; i <= 6; ++i)
        sum = (sum + f[cur][i]) % MOD;

    // d = 4 ^ n;
    LL res = 1;
    LL b = 4;
    int p = n;

    while (p) {
        if (p & 1) res = (res * b) % MOD;
        b = (b * b) % MOD;
        p >>= 1;
    }
    //cout << res << ' ' << sum << endl;
    cout << (res * sum) % MOD;
    return 0;
}

dfs

#include <iostream>

using namespace std;

typedef long long LL;

const int MOD = 1e9+7;

int n, m;
int op[10]; // 筛子对应的面
bool con[10][10]; // 是否冲突

void init() {
    op[1] = 4;
    op[4] = 1;
    op[2] = 5;
    op[5] = 2;
    op[3] = 6;
    op[6] = 3;
}

LL dfs(int up, int cnt) {
    if (cnt == n) return 1;

    LL ans = 0;
    for (int i = 1; i <= 6; ++i) {
        int down = op[up];
        if (con[down][i] || con[i][down]) continue;
        ans = (ans + 4 * dfs(i, cnt + 1)) % MOD;
    }
    return ans;
}

int main(void) {
    init();
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        con[a][b] = true;
        con[b][a] = true;
    }

    LL ans = 0;
    for (int i = 1; i <= 6; ++i) {
        ans = (ans + 4 * dfs(i, 1)) % MOD;
    }

    cout << ans;
    return 0;

}