指数型生成函数，推一推可得：
\[(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...)^2+(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+...)^2
\]
\]
\[=e^{2x}+(\frac{e^x+2^-x}{2})^2
\]
\]
\[=e^{2x}+\frac{e^{2x}+e^{-2x}+2}{4}
\]
\]
\[=\frac{e^{4x}+2e^{2x}+1}{4}
\]
\]
因为
\[e^x=\sum_{i=0}^{inf}\frac{x^i}{i!},e^{4x}=\sum_{i=0}^{inf}\frac{(4x)^i}{i!}=\sum_{i=0}^{inf}\frac{4^ix^i}{i!}
\]
\]
所以展开可得
\[=\frac{1}{4}+\frac{\sum_{i=0}^{inf}\frac{4^ix^i}{i!}+2*\sum_{i=0}^{inf}\frac{2^ix^i}{i!}}{4}
\]
\]
\[=\frac{1}{4}+\frac{\sum_{i=0}^{inf}(4^i+2^{i+1})*\frac{x^i}{i!}}{4}
\]
\]
前面的常数不用管，这样取i个的答案也就是第i项的系数就是\( 4i+2{i+1} \)
#include<iostream>
#include<cstdio>
using namespace std;
const int mod=10007;
int T,n;
int ksm(int a,int b)
{
int r=1;
while(b)
{
if(b&1)
r=r*a%mod;
a=a*a%mod;
b>>=1;
}
return r;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%d\n",(ksm(2,n-1)+ksm(4,n-1))%mod);
}
return 0;
}