Codeforces 268D

#include
#include
#include
using namespace std;
const int mod=1e9+9;
typedef __int64 LL;
LL dp[1010][2][31][31][31];
void fm(LL &x){
    if(x>mod)x-=mod;
}
int main(){
    #ifdef DouBi
    freopen("in.cpp","r",stdin);
    #endif // DouBi
    int n,h;while(scanf("%d%d",&n,&h)!=EOF){
        memset(dp,0,sizeof(dp));
        dp[0][0][0][0][0]=1;
        LL val;
        for(int i=0;ifor(int a=0;a<=1;a++){
                for(int b=0;b<=h;b++){
                    for(int c=0;c<=h;c++){
                        for(int d=0;d<=h;d++)if(val=dp[i][a][b][c][d]){
                            dp[i+1][a][b+11:h][c+11:h][d+11:h]+=dp[i][a][b][c][d];   fm(dp[i+1][a][b+11:h][c+11:h][d+11:h]);
                            dp[i+1][b+1<=h?0:1][c+11:h][d+11:h][a?h:1]+=dp[i][a][b][c][d];fm(dp[i+1][b+1<=h?0:1][c+11:h][d+11:h][a?h:1]);
                            dp[i+1][c+1<=h?0:1][d+11:h][a?h:1][b+11:h]+=dp[i][a][b][c][d];fm(dp[i+1][c+1<=h?0:1][d+11:h][a?h:1][b+11:h]);
                            dp[i+1][d+1<=h?0:1][a?h:1][b+11:h][c+11:h]+=dp[i][a][b][c][d];fm(dp[i+1][d+1<=h?0:1][a?h:1][b+11:h][c+11:h]);
                        }
                    }
                }
            }
        }
        //printf("%I64d
",dp[1][0][1][1][1]);
        LL ans=0;
        for(int a=0;a<=1;a++){
            for(int b=0;b<=h;b++){
                for(int c=0;c<=h;c++){
                    for(int d=0;d<=h;d++){
                        if(!a||b//if(n==2&&dp[n][a][b][c][d])printf("%d %d %d %d %I64d
",a,b,c,d,dp[n][a][b][c][d]);
                            ans+=dp[n][a][b][c][d];fm(ans);
                        }
                    }
                }
            }
        }
        printf("%I64d
",ans);
    }
    return 0;
}