hdu2606（递推）

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 19890907
#define inf 0x3f3f3f3f
#define N 10010
using namespace std;
int f[110];
void init()
{
    f[0]=1;f[1]=1;f[2]=5;f[3]=13;
    for(int i=4;i<=100;i++)
    {
        f[i]=(f[i-4]+f[i-3]*2+f[i-2]*4+f[i-1])%mod;
        for(int j=3;j<=i;j++)f[i]=(f[i]+2*f[i-j])%mod;
    }
}
int main()
{
    int n,t;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",f[n]);
    }
}