hdu 4301 简单DP

/*
相同数字表示被分在一起
      x -> x+1
      0    00   01   00   01   01
      0 -> 00 , 01 , 01 , 00 , 02
块数；y    y    y+1  y+1  y+1  y+2
      0    02   01   00   00   02   00   02
      1 -> 12 , 11 , 10 , 11 , 11 , 12 , 13
块数；y    y+1  y    y    y    y+1  y+1  y+2
*/
#include<cstdio>
#define MAXN 1010
#define Mod 100000007//要看清题目，开始习惯性的以为是1000000007 
int DPf[MAXN][MAXN<<1],DPh[MAXN][MAXN<<1];
int main()
{
    int t,n,k;
    scanf("%d",&t);
    DPf[1][2]=DPh[1][1]=1;
    for(int i=2;i<MAXN;i++){
        DPh[i][1]=1;
        for(int j=2;j<=i*2;j++){
            DPh[i][j]=(DPh[i-1][j]+DPh[i-1][j-1]+DPf[i-1][j-1]+DPf[i-1][j]*2)%Mod;
            DPf[i][j]=(DPh[i-1][j-2]+DPh[i-1][j-1]*2+DPf[i-1][j-2]+DPf[i-1][j-1]*2+DPf[i-1][j])%Mod;
        }
    }
    while(t--){
        scanf("%d%d",&n,&k);
        printf("%d\n",(DPf[n][k]+DPh[n][k])%Mod);
    }
    return 0;
}