# 垒骰子

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

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

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

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

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

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

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

不要小看了 atm 的骰子数量哦～  


**输入格式**

第一行两个整数 n m  

n表示骰子数目  

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


**输出格式**

一行一个数，表示答案模 $10^9 + 7$ 的结果。


**样例输入**

```
2 1
1 2
```

**样例输出**

```
544
```


**数据范围**

```
对于 30% 的数据：n <= 5
对于 60% 的数据：n <= 100
对于 100% 的数据：0 < n <= 10^9, m <= 36
```


**资源约定：**

峰值内存消耗 < 256M  
CPU消耗  < 2000ms


以下选项<span style="color:red">错误</span>的是？

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
#define MOD 1000000007
using namespace std;

int points[7] = {0, 4, 5, 6, 1, 2, 3};
int n, m;
int ban[36][2];
long long result;

bool judge(int point1, int point2)
{
    bool flag = true;
    for (int i = 0; i < m; i++)
    {
        int point3 = points[point2];
        if (point1 == ban[i][0] && point3 == ban[i][1])
        {

            flag = false;
            break;
        }
        if (point1 == ban[i][1] && point3 == ban[i][0])
        {

            flag = false;
            break;
        }
    }
    return flag;
}

void dfs(int cnt, int point)
{
    if (cnt == n)
    {
        result++;
        return;
    }
    for (int i = 1; i <= 6; i++)
    {
        if (judge(point, i))
        {
            cnt++;
            dfs(cnt, i);
            cnt--;
        }
    }
}

long long quickpow(int x, int N)
{
    int reg = x;
    int sum = 1;
    while (N)
    {
        if (N & 1)
        {
            sum = sum * reg;
        }
        reg *= reg;
        N = N >> 1;
    }
    return sum;
}
int main()
{

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> ban[i][0] >> ban[i][1];
    }
    dfs(0, 0);

    long long temp = quickpow(4, n);
    cout << result * temp % MOD;
    return 0;
}
```

## 选项

### A

```c
#define MOD 1000000007

typedef long long LL;
LL dp[2][7];
int n, m;
bool conflict[7][7];
map<int, int> op;

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

struct M
{
    LL a[6][6];

    M()
    {
        for (int i = 0; i < 6; ++i)
        {
            for (int j = 0; j < 6; ++j)
            {
                a[i][j] = 1;
            }
        }
    }
};

M mMultiply(M m1, M m2)
{
    M ans;

    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            ans.a[i][j] = 0;
            for (int k = 0; k < 6; ++k)
            {
                ans.a[i][j] = (ans.a[i][j] + m1.a[i][k] * m2.a[k][j]) % MOD;
            }
        }
    }
    return ans;
}

M mPow(M m, int k)
{
    M ans;
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            if (i == j)
                ans.a[i][j] = 1;
            else
                ans.a[i][j] = 0;
        }
    }
    while (k)
    {
        if (k & 1)
        {
            ans = mMultiply(ans, m);
        }
        m = mMultiply(m, m);
        k >>= 1;
    }
    return ans;
}

int main()
{
    init();
    scanf("%d%d", &n, &m);
    M cMatrix;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        cMatrix.a[op[a] - 1][b - 1] = 0;
        cMatrix.a[op[b] - 1][a - 1] = 0;
    }

    M cMatrix_n_1 = mPow(cMatrix, n - 1);

    LL ans = 0;
    for (int j = 0; j < 6; ++j)
    {
        for (int i = 0; i < 6; ++i)
        {
            ans = (ans + cMatrix_n_1.a[i][j]) % MOD;
        }
    }

    LL t = 1;
    LL tmp = 4;
    LL p = n;
    while (p)
    {
        if (p & 1)
        {
            t = t * tmp % MOD;
        }
        tmp = tmp * tmp % MOD;
        p >>= 1;
    }
    printf("%lld", ans * t % MOD);

    return 0;
}
```

### B

```c
#define MOD 1000000007

typedef long long LL;
LL dp[2][7];
int n, m;
bool conflict[7][7];
map<int, int> op;

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

int main()
{
    init();
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        conflict[a][b] = true;
        conflict[b][a] = true;
    }

    for (int j = 1; j <= 6; ++j)
    {
        dp[0][j] = 1;
    }

    int cur = 0;

    for (int level = 2; level <= n; ++level)
    {
        cur = 1 - cur;

        for (int j = 1; j <= 6; ++j)
        {
            dp[cur][j] = 0;

            for (int i = 1; i <= 6; ++i)
            {
                if (conflict[op[j]][i])
                    continue;
                dp[cur][j] = (dp[cur][j] + dp[1 - cur][i]) % MOD;
            }
        }
    }

    LL sum = 0;
    for (int k = 1; k <= 6; ++k)
    {
        sum = (sum + dp[cur][k]) % MOD;
    }

    LL ans = 1;
    LL tmp = 4;
    LL p = n;

    while (p)
    {
        if (p & 1)
            ans = (ans * tmp) % MOD;
        tmp = (tmp * tmp) % MOD;
        p >>= 1;
    }
    printf("%lld\n", (sum * ans) % MOD);
    return 0;
}
```

### C

```c
#define MOD 1000000007

int op[7];
bool confilct[7][7];
void init()
{
    op[1] = 4;
    op[4] = 1;
    op[2] = 5;
    op[5] = 2;
    op[3] = 6;
    op[6] = 3;
}
int n, m;

long long int f(int up, int count)
{
    if (count == 0)
        return 4;
    long long ans = 0;
    for (int upp = 1; upp <= 6; ++upp)
    {
        if (confilct[op[up]][upp])
            continue;
        ans = (ans + f(upp, count - 1)) % MOD;
    }
    return ans;
}

int main()
{
    init();
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        confilct[y][x] = true;
        confilct[x][y] = true;
    }
    long long ans = 0;
    for (int up = 1; up <= 6; ++up)
    {
        ans = (ans + 4 * f(up, n - 1)) % MOD;
    }
    printf("%lli\n", ans);
    return 0;
}
```