# 【GDOI2018模擬7.12】B

1

229

## Code

``````#include <cstdio>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for(int i=a;i<=b;i  )
#define N 10
#define mo 1000000007
#define ll long long
using namespace std;
int dd[5][2]={0,0,1,0,-1,0,0,1,0,-1},e[N],bz[N];
ll ans,d[N][N],a[N][N],b[N][N],c[N][N],n;
int get(int x,int y){return (x-1)*3 y;}
void cl()
{
fo(i,1,9) fo(j,1,9) c[i][j]=a[i][j],a[i][j]=0;
}
void ch1()
{
cl();
fo(i,1,9) fo(j,1,9) fo(k,1,9) a[i][k]=(a[i][k] c[i][j]*b[j][k])%mo;
}
void ch()
{
cl();
fo(i,1,9) fo(j,1,9) fo(k,1,9) a[i][k]=(a[i][k] c[i][j]*c[j][k])%mo;
}
void mi(ll x)
{
if(x<2) return;
fo(i,1,9) fo(j,1,9) b[i][j]=a[i][j];
mi(x/2);
ch();
if(x%2==1) ch1();
}
void dg(int x)
{
if(x>9)
{
ll an=1;
fo(i,1,9) an=(an*d[i][e[i]])%mo;
ans=(ans an)%mo;
return;
}
fo(i,1,9) if(!bz[i]) bz[i]=1,e[x]=i,dg(x 1),bz[i]=0;
}
int main()
{
scanf("%lld",&n);
fo(i,1,3) fo(j,1,3)
{
fo(k,0,4)
{
int x=i dd[k][0],y=j dd[k][1];
if(x>0&&y>0&&x<4&&y<4)
{
a[get(i,j)][get(x,y)]=1;
}
}
}
mi(n);
fo(i,1,9) fo(j,1,9) b[i][j]=a[i][j];
fo(i,1,9)
{
memset(a,0,sizeof(a));
a[1][i]=1;
ch1();
fo(j,1,9) d[i][j]=a[1][j];
}
ans=0;
dg(1);
printf("%lld\n",ans);
}``````