【题意】

有n个方块，现用红黄蓝绿四种颜色将他们染色，要求红色的方块和蓝色的方块个数均为偶数个，求方案数 mod 10007。

【解题方法】

如果粉刷到第i个墙砖时，使用的红色墙砖和蓝色墙砖都是偶数的方法

数有ai，使用的红色和蓝色墙砖一奇一偶的方案数为bi，使用的红色和蓝色墙砖都是奇数的

方案数为ci，那么，我们easy得到以下的递推式:





对于求取ai，我们可通过计算对应矩阵的幂得知，计算矩阵的幂，利用高速二分幂，

可将时间复杂度降为O(lgn).


【AC code】 
//POJ.3734
//Blocks

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod=10007;
struct Matrix{
    int a[3][3];
}A,B;
Matrix operator*(const Matrix &a,const Matrix &b)
{
    Matrix c;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            c.a[i][j]=0;
            for(int k=0; k<3; k++)
            {
                c.a[i][j]=(c.a[i][j]%mod+((a.a[i][k]%mod)*(b.a[k][j])%mod)%mod)%mod;
            }
        }
    }
    return c;
}
Matrix pow(Matrix a,int x)
{
    Matrix c;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            if(i==j) c.a[i][j]=1;
            else     c.a[i][j]=0;
        }
    }
    while(x)
    {
        if(x&1) c=c*a;
        a=a*a;
        x>>=1;
    }
    return c;
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        A.a[0][0]=2,A.a[0][1]=1,A.a[0][2]=0;
        A.a[1][0]=2,A.a[1][1]=2,A.a[1][2]=2;
        A.a[2][0]=0,A.a[2][1]=1,A.a[2][2]=2;
        B.a[0][0]=1,B.a[1][0]=0,B.a[2][0]=0;
        A=pow(A,n);
        A=A*B;
        printf("%d\n",A.a[0][0]%mod);
    }
}