Codeforces268D. Wall Bars 五维dp

题目：D. Wall Bars

time limit per test

4 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Manao is working for a construction company. Recently, an order came to build wall bars in a children's park. Manao was commissioned to develop a plan of construction, which will enable the company to save the most money.

After reviewing the formal specifications for the wall bars, Manao discovered a number of controversial requirements and decided to treat them to the company's advantage. His resulting design can be described as follows:

• Let's introduce some unit of length. The construction center is a pole of height n.
• At heights 1, 2, ..., n exactly one horizontal bar sticks out from the pole. Each bar sticks in one of four pre-fixed directions.
• A child can move from one bar to another if the distance between them does not exceed h and they stick in the same direction. If a child is on the ground, he can climb onto any of the bars at height between 1 and h. In Manao's construction a child should be able to reach at least one of the bars at heights n - h + 1, n - h + 2, ..., n if he begins at the ground.

The figure to the left shows what a common set of wall bars looks like. The figure to the right shows Manao's construction

Manao is wondering how many distinct construction designs that satisfy his requirements exist. As this number can be rather large, print the remainder after dividing it by 1000000009 (109 + 9). Two designs are considered distinct if there is such height i, that the bars on the height i in these designs don't stick out in the same direction.

Input

A single line contains two space-separated integers, n and h (1 ≤ n ≤ 1000, 1 ≤ h ≤ min(n, 30)).

Output

In a single line print the remainder after dividing the number of designs by 1000000009 (109 + 9).

Examples

input

Copy

5 1

output

Copy

4

input

Copy

4 2

output

Copy

148

input

Copy

4 3

output

Copy

256

input

Copy

5 2

output

Copy

376

Note

Consider several designs for h = 2. A design with the first bar sticked out in direction d1, the second — in direction d2 and so on (1 ≤ di ≤ 4) is denoted as string d1d2...dn.

Design "1231" (the first three bars are sticked out in different directions, the last one — in the same as first). A child can reach neither the bar at height 3 nor the bar at height 4.

Design "414141". A child can reach the bar at height 5. To do this, he should first climb at the first bar, then at the third and then at the fifth one. He can also reach bar at height 6 by the route second  →  fourth  →  sixth bars.

Design "123333". The child can't reach the upper two bars.

Design "323323". The bar at height 6 can be reached by the following route: first  →  third  →  fourth  →  sixth bars.

题意有一个长度为n的杆子从1~n的每个节点可以伸出一个杆子来这个杆子可以指向东南西北四个方向中的任意一个方向。有一个猴他每次跳跃的高度最大为h，他在地面上时可以跳向高度小于h的任意一个杆(不论方向),但是他跳到杆子上之后就只能延当前方向跳，结束的条件就是他能跳到n-h+1~n这些高度中的任意一个，假设你是一个设计师问你一共有多少种设计方案能使这只猴达成目标。

dp[i][a][b][c][d];表示建造到第i层，a表示所选的主要面(猴子爬的那一面)是否可达1表示可达，0不可达然后bcd分别表示另外三个面到当前阶层的距离，如果说相差大于h那么就和h没有差别了都是跳不上去那么就把另外3维降成了30要不五维数组开都开不了。

一开始我比较困惑如何将这一层的主要面转换成下一层的次要面，因为只有主要面是0，1次要面是0~h然后明白如果说他能到达那么那么第i层距离第i+1层肯定就是1否则就说明i层之前肯定有断层即无法继续往上爬所以直接就令他等于h即可。

#include<bits/stdc++.h>
using namespace std;
const long long inf=1000000009;
long long dp[1001][2][31][31][31];
int main(){int n,h;cin>>n>>h;memset(dp,0,sizeof(dp));dp[0][1][0][0][0]=1;for(int i=0;i<n;i++){for(int a=0;a<2;a++){for(int b=0;b<=h;b++){for(int c=0;c<=h;c++){for(int d=0;d<=h;d++){dp[i+1][a][min(b+1,h)][min(c+1,h)][min(d+1,h)]=(dp[i+1][a][min(b+1,h)][min(c+1,h)][min(d+1,h)]+dp[i][a][b][c][d])%inf;dp[i+1][b+1<=h?1:0][a?1:h][min(c+1,h)][min(d+1,h)]=(dp[i+1][b+1<=h?1:0][a?1:h][min(c+1,h)][min(d+1,h)]+dp[i][a][b][c][d])%inf;dp[i+1][c+1<=h?1:0][min(b+1,h)][a?1:h][min(d+1,h)]=(dp[i+1][c+1<=h?1:0][min(b+1,h)][a?1:h][min(d+1,h)]+dp[i][a][b][c][d])%inf;dp[i+1][d+1<=h?1:0][min(b+1,h)][min(c+1,h)][a?1:h]=(dp[i+1][d+1<=h?1:0][min(b+1,h)][min(c+1,h)][a?1:h]+dp[i][a][b][c][d])%inf;}}}}}long long ans=0;for(int i=0;i<2;i++){for(int j=0;j<=h;j++){for(int k=0;k<=h;k++){for(int l=0;l<=h;l++){if(i==1||j<h||k<h||l<h){ans+=dp[n][i][j][k][l];if(ans>inf)ans-=inf;}}}}}cout<<ans<<endl;}