题目描述

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。

经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！

我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。

假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。

atm想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。

由于方案数可能过多，请输出模 109+7 的结果。

输入格式
第一行包含两个整数 n,m，分别表示骰子的数目和排斥的组数。

接下来 m 行，每行两个整数 a,b，表示 a 和 b 数字不能紧贴在一起。

输出格式
共一个数，表示答案模 109+7 的结果。

数据范围
1≤n≤109,
1≤m≤36,
1≤a,b≤6

样例

输入样例：

2 1
1 2

输出样例：

544

Tips：

1.状态设置为当前朝上的点数是多少；

2.每个点数面朝上的，它的四周的朝向特定方向的点数都有四种可能；

3.所以一个骰子点数朝上有六种，而每种又有四种小情况朝向特定方向点数不同，一共24种；

4.若骰子每个面都不排斥的话，从点数为1的面朝上，到点数为2的面朝上，也会有四种情况
若1与2的对立面5排斥，则加入一个骰子，从点数为1的面朝上，到点数为2的面朝上这种情况
不可能会发生，所以该状态的转移从4种可能变为0种可能；

5.数组从0开始，所以把骰子点数都减去一，把p[6][6]转移矩阵都设置为4，若有面互斥，则
把转移可能的结果由4种变为零种；

6.若垒了两个骰子，则第一个骰子面朝上的点数有六种可能，再加入一个骰子，1朝上可会变为[1 - 6]朝上
的任何一种，同理，第一个骰子[2 - 6]朝上也一样，p[i][j]表示从i朝上变为j点朝上的可能数，将一个骰子所有
可能的1 * 6 的状态矩阵分别乘以p矩阵，即可得到骰子为二的所有方案，同理，骰子为三时再把骰子为二的方案
矩阵再乘以p矩阵即可；所以垒N个骰子的方案 = 骰子一个时的方案矩阵 乘以 p转移矩阵的^(N-1)；

C++ 代码

#include<iostream>
#include<cstring>

typedef long long ll;
const int mod = 1e9 + 7;
ll mp[6][6] = { {} };
int N, K;
int back[6] = { 3,4,5,0,1,2 };
ll ans[6][6] = { {} };
ll ali[6] = { 4,4,4,4,4,4 };

void pow_2(ll ans[6][6])
{
    ll tmp[6][6] = { {} };
    for (int i = 0; i < 6; i++)
        for (int m = 0; m < 6; m++)
            for (int n = 0; n < 6; n++)
                tmp[i][m] += (ans[i][n] % mod * mp[n][m] % mod) % mod, tmp[i][m] %= mod;
    memcpy(ans, tmp, sizeof(tmp));
    return;
}

void pow_2()
{
    ll tmp[6][6] = { {} };
    for (int i = 0; i < 6; i++)
        for (int m = 0; m < 6; m++)
            for (int n = 0; n < 6; n++)
                tmp[i][m] += (mp[i][n] % mod * mp[n][m] % mod) % mod, tmp[i][m] %= mod;
    memcpy(mp, tmp, sizeof(tmp));
    return;
}


ll quick(int n)
{
    int first = 1;
    while (n)
    {
        if (n & 1)
        {
            if (first)memcpy(ans, mp, sizeof(mp));
            else pow_2(ans);
            first = 0;
        }
        n >>= 1;
        pow_2();
    }
    ll now = 0;
    ll ks[6] = {};
    for (int i = 0; i < 6; i++)
        for (int m = 0; m < 6; m++)
            ks[i] += (ali[m] % mod * ans[m][i] % mod) % mod, ks[i] %= mod;
    for (int i = 0; i < 6; i++)
        now += ks[i], now %= mod;

    return now;
}

int main(void)
{
    std::ios_base::sync_with_stdio(false);
    for (int i = 0; i < 6; i++)
        for (int m = 0; m < 6; m++)
            mp[i][m] = 4;
    std::cin >> N >> K;
    while (K--)
    {
        int a, b;
        std::cin >> a >> b;
        a--, b--;
        mp[a][back[b]] = 0;
        mp[b][back[a]] = 0;
    }
    if (N - 1)std::cout << quick(N - 1);
    else std::cout << 24;
    return 0;
}