Description
众所周知，度度熊最近沉迷于 Pokémon GO。
今天它决定要抓住所有的精灵球！
为了不让度度熊失望，精灵球已经被事先放置在一个2*N的格子上，每一个格子上都有一个精灵球。度度熊可以选择任意一个格子开始游戏，抓捕格子上的精灵球，然后移动到一个相邻的至少有一个公共点的格子上继续抓捕。例如，(2, 2) 的相邻格子有(1, 1), (2, 1) 和 (1, 2) 等等。
现在度度熊希望知道将所有精灵球都抓到并且步数最少的方案数目。两个方案被认为是不同，当且仅当两个方案至少有一步所在的格子是不同的。
Input
第一行为T，表示输入数据组数。
每组数据包含一个数N。
1≤T≤100
1≤N≤10000
Output
对每组数据输出方案数目，结果对 1 000 000 007 取模。
Sample Input
3
1
2
3
Sample Output
2
24
96
思路
显然，步数最少的方案当然是所有格子只访问一遍咯！
我们设 $B_n$ 代表从某个角出发，然后走遍所有格子回到同一列的方案数目。
显然：
$B_1=1$
$B_n=2\times B_{n-1}=2^{n-1}$
同样，我们设 $A_n$ 代表从某个角出发，然后走遍所有格子的方案数。
则 $A_n=B_n+2 \times A_{n-1}+4 \times A_{n-2}$
其中 $B_n$ 代表回到了当前列的方案数， $A_{n-1}$ 代表先填满当前列然后走到相邻的列处理同样的一个子问题， $A_{n-2}$ 代表通过对角线方式先走完当前列与相邻列的格子，然后剩下的 $n-2$ 列即相同子问题。
因为有四个角，所以我们的结果要乘以 $4$ ，即 $4 \times A_n$ 。
当然，真实情况下我们不一定是从四个角出发的，还有另一种情况就是中间的列咯。
考虑中间的第 $i$ 列
我们可以先从第 $i$ 列往左走完所有的格子回来，然后再往右走完所有的格子；
也可以先往右走完所有的格子回来，再往左走完所有的格子。
于是总的方案数即 $2 \times(4\times B_{i-1}\times A_{n-i}+4 \times B_{n-i}\times A_{i-1})$ ，其中 $2$ 代表第 $i$ 列有两个格子可选为初始点， $4$ 代表分别向左右两边行走时的选择方案数 $2 \times 2$ 。
AC 代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn =1e5+10;
const int mod = 1e9+7;
LL a[maxn],b[maxn];
void init()
{
b[1]=1;
for (int i=2; i<maxn; i++)
b[i]=(b[i-1]*2%mod);
a[1]=1;
a[2]=6;
for (int i=3; i<maxn; i++)
a[i]=(2*a[i-1]+b[i]+4*a[i-2])%mod;
}
int main()
{
init();
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
if(n==1)
{
cout<<2<<endl;
continue;
}
LL sum=4*a[n];
for (int i=2; i<n; i++)
sum=(((8*b[n-i]*a[i-1])%mod+(8*a[n-i]*b[i-1])%mod)%mod+sum)%mod;
cout<<sum<<endl;
}
return 0;
}
