原题链接

题解

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll a[7][7]={0},e[7]={0};

void cf1()
{
    ll tem[7]={0};
    for(int i=1;i<=6;i++)
    {
        for(int j=1;j<=6;j++)
        {
            tem[i]+=a[i][j]*e[j];
            tem[i]%=mod;
        }
    }

    for(int i=1;i<=6;i++) e[i]=tem[i];
}

void cf2()
{
    ll tem[7][7]={0};
    for(ll i=1;i<=6;i++)
    {
        for(ll j=1;j<=6;j++)
        {
            for(ll k=1;k<=6;k++)
            {
                tem[i][j]+=a[i][k]*a[k][j];
                tem[i][j]%=mod;
            }
        }
    }

    for(ll i=1;i<=6;i++)
        for(ll j=1;j<=6;j++) a[i][j]=tem[i][j];
}
int main()
{
    ll n,m;
    cin>>n>>m;

    for(ll i=1;i<=6;i++)
    {
        e[i]=4;
        for(ll j=1;j<=6;j++) a[i][j]=a[j][i]=4;
    }

    for(ll i=1;i<=m;i++)
    {
        ll x,y;
        cin>>x>>y;
        ll x1=(x+2)%6+1,y1=(y+2)%6+1;
        a[x1][y]=0;
        a[y1][x]=0;
    }

    ll tem=n-1;
    while(tem)
    {
        if(tem&1) cf1();
        cf2();
        tem>>=1;
    }

    ll ans=0;
    for(ll i=1;i<=6;i++)
    {
        ans+=e[i];
        ans%=mod;
    }
    cout<<ans;
    return 0;
}