对于一排n个正方形，有f(n)种方案达成目标，若第n个块是白色，则有f(n-1)种方案，若第n个块是黑色，则第n-1个块必为白色，那么有f(n-2)+n-2种方案。
则f(n)=f(n-1)+f(n-2)+n-2 。
写成矩阵形式：
(http://img.blog.csdn.net/20161011211956406)
例如：(i,j)表示i个空涂j个的种类数
(9,2)=(7,1)+(6,1)+(5,1)+(4,1)+(3,1)+(2,1)+(1,1)
(9,3)=(7,2)+(6,2)+(5,2)+(4,2)+(3,2)
(9,4)=(7,3)+(6,3)+(5,3)
(9,5)=(7,4)
(8,2)=(6,1)+(5,1)+(4,1)+(3,1)+(2,1)+(1,1)
(8,3)=(6,2)+(5,2)+(4,2)+(3,2)
(8,4)=(6,3)+(5,3)
#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=1e9+;
struct Mat
{
ll mat[][];
};
Mat Mult(Mat a,Mat b)
{
Mat c;
memset(c.mat,,sizeof(c.mat));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
return c;
} Mat QMult(Mat a,ll b)
{
Mat c;
for(int i=;i<;i++)
for(int j=;j<;j++)
c.mat[i][j]=i==j;
while(b){
if(b&)
c=Mult(c,a);
a=Mult(a,a);
b>>=;
}
return c;
} int main()
{
ll n;
while(~scanf("%lld",&n))
{
Mat res;
if(n==)
{
puts("");
continue;
}
else if(n==)
{
puts("");
continue;
}
memset(res.mat,,sizeof(res.mat));
res.mat[][]=res.mat[][]=res.mat[][]=res.mat[][]=;
res.mat[][]=res.mat[][]=res.mat[][]=;
res=QMult(res,n-);
printf("%lld\n",(res.mat[][]+*res.mat[][]+res.mat[][])%mod);
}
return ;
}