顶好的一道题。其实，是POJ 2411的升级版。但POJ 2411我用的插头DP来做，一时没想到那道题怎么用状态DP，于是回头看POJ 2411那一道的状态DP，其实也很简单，就是每一行都设一个状态，用位来表示，如果上一行为0，则当前行必定是要竖着放的。填1.否则，当前行的位置可以横放填两个格子为1，也可以不放，为0.于是，看上一行的状态能转移到哪些状态，就可以了。
这一道也是一样的想做法，DFS看开始时有哪些状态，记在一个一维矩阵里。因为有一些状态最开始是达不到的，如奇数个1，或者一些不连续1的状态。然后求转移矩阵（这个地方想了很久才想到，因为要做很多重复的工作，所以想到用矩阵）。求矩阵时，也用DFS就可以了。
此处在矩阵相乘时有一个小优化，因为转移矩阵中含0较多，所以把中间变量K提到第一个循环。当含有0时就终止。因为这个地方由TLE，优化到了8000MS，也是满足了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL __int64
#define mod 1000000007
using namespace std;
struct Matrix{
LL ans[130][130];
};
Matrix pp[31];
LL bgn[130];
LL res[130];
int only;
int number[260];
Matrix transfer;
Matrix per;
bool ok(int s){
int c=0;
for(int i=0;i<8;i++)
if(s&(1<<i)) c++;
if(c%2==0) return true;
return false;
}
Matrix operator *(Matrix a,Matrix b){
Matrix c;
for(int i=0;i<only;i++)
for(int j=0;j<only;j++)
c.ans[i][j]=0;
for(int k=0;k<only;k++) //把k提到这里来就过了。。。哈哈，这也是一种优化啊，因为矩阵中0较多，避免了不必要的计算。
for(int i=0;i<only;i++){
if(a.ans[i][k]==0) continue;
for(int j=0;j<only;j++){
c.ans[i][j]=(c.ans[i][j]+(a.ans[i][k]*b.ans[k][j])%mod)%mod;
}
}
return c;
}
void find_bgn(int state,int pos){
if(pos>=8) {
bgn[number[state]]++;
return ;
}
int tmp=state;
int i=pos;
if((state&(1<<i))==0&&(state&(1<<((i+1)%8)))==0){
tmp=state|(1<<i)|(1<<((i+1)%8));
find_bgn(tmp,i+2);
}
find_bgn(state,i+1);
}
void dfs(int pre,int state,int pos){
if(pos>=8) {
transfer.ans[number[pre]][number[state]]++;
return ;
}
int tmp=state;
int i=pos;
if((state&(1<<i))==0&&(state&(1<<((i+1)%8)))==0){
tmp=state|(1<<i)|(1<<((i+1)%8));
dfs(pre,tmp,i+2);
}
dfs(pre,state,i+1);
}
/*
LL can(int a,int b)
{
int st,i,j;
bool end=false;
if(a==0)return b==255? 1LL:0;
for(i=0;i<8;i++)
{
j=(i+7)%8;
if((a&(1<<i))&&(a&(1<<j))==0)
{
st=i;
break;
}
}
for(i=st;i!=st||end==false;i=(i+1)%8)
{
end=true;
j=(i+1)%8;
if(0==(a&(1<<i)))
{
if(0==(b&(1<<i)))return 0;
}
else
{
if((a&(1<<j))&&(b&(1<<i))&&(b&(1<<j)))i++;
else if((b&(1<<i))==0)continue;
else return 0;
}
}
return 1LL;
}
*/
void initial(){
only=0;
memset(number,-1,sizeof(number));
memset(transfer.ans,0,sizeof(transfer.ans));
for(int i=0;i<(1<<8);i++)
if(ok(i)) number[i]=only++;
for(int i=0;i<only;i++)
for(int j=0;j<only;j++)
if(i==j) per.ans[i][i]=1;
else per.ans[i][j]=0;
memset(bgn,0,sizeof(bgn));
find_bgn(0,0);
for(int i=0;i<(1<<8);i++){
if(number[i]!=-1){
dfs(i,255-i,0);
}
}
/*
for(int i=0;i<1<<8;i++)
for(int j=i+1;j<1<<8;j++)
if(number[i]!=-1&&number[j]!=-1)
transfer.ans[number[j]][number[i]]=transfer.ans[number[i]][number[j]]=can(i,j);
transfer.ans[only-1][only-1]=2;
*/
for(int i=1;i<31;i++){
if(i==1)
pp[i]=transfer;
else
pp[i]=pp[i-1]*pp[i-1];
}
}
LL pow(int k){
Matrix ans=per,ats=transfer;
int c=1;
while(k){
if(k&1) ans=ans*pp[c];
k>>=1;
c++;
}
LL tmp=0;
for(int j=0;j<only;j++)
tmp=(tmp+(bgn[j]*ans.ans[j][only-1])%mod)%mod;
return tmp;
}
int main(){
initial();
int n,T,kase=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
LL resul=pow(n-1);
printf("Case %d: %I64d
",++kase,resul);
}
return 0;
}