Coloring Game（水题，快速幂）_综合

本题题意是给一个2×N的格子阵，要从左上角走到右下角，规定了8种移动方向。这是一道找规律的题，我们分析一下这个图：

首先左上角和右下角肯定要走，这两个格子不用考虑
中间的N-2列，每列有两个格子，两个格子都有走或者不走两种选择。但是如果两个都不走，那么就无法从左上角走到右下角。所以每一列都有三种选择：走上面的格子、走下面的格子、两个格子都走。所以中间的N-2列有 $3^{N-2}$ 中走法。
最后是左下角和右上角，这两个格子比较特殊，因为左上角和右下角是必走的，所以这两个格子都是可以走或者不走，那么就有4种情况。
若N=1，即只有一列，那么就只有一种走法，这是一种特殊情况。

所以本题的规律就是 $4\times 3^{N-2}$ ，下面就是写一个快速幂，再注意一下N=1这种情况就可以了。代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
ll PowMod(ll a,ll b,ll c)
{ll result=1;ll base=a%c;while(b){if(b&1)result=(result*base)%c;base=(base*base)%c;b>>=1;}return result;
}
int main()
{ll n,res=0,t=1;cin>>n;if(n==1)cout<<1<<endl;elsecout<<(4*PowMod(3,n-2,1000000007))%1000000007<<endl;return 0;
}