Wall Bars

题意翻译

## 题目描述 Manao 正在一家建筑公司工作。最近这家公司要在一个儿童公园建造墙杆。Manao 受委托制定一项建造计划。 Manao 的正确设计描述如下： - 建筑中心是一根高度为 $n$ 的主杆。 - 在高度 $1, 2, ..., n$ 处，正好有一根水平横杠从主杆上伸出。每根横杠都会向四个方向中的一个方向突出。 - 孩子可以从一根栏杆爬到另一根横杠，当且仅当它们之间的高度差不超过 $h$，并且它们突出在同一个方向。如果一个孩子在地上，他可以在 $1$ 到 $h$ 之间的高度爬到任何一个横杠上。在 Manao 的设计中，一个孩子应该能够在高度 $n - h + 1, n - h + 2, ..., n$ 爬到至少一个横杠，并且他从地面开始爬。  上图是一个建造示例。 Manao 想知道，有多少种建筑满足要求？由于答案可能非常大，**所以对 $10^9 + 9$ 取模**。如果有这样的高度 $i$，则两种设计被认为是不同的，即这些设计中高度 $i$ 上的横杠不会朝同一方向突出。 ## 输入格式 一行包括两个整数 $n, k(1 \le n \le 1000, 1 \le h \le \min(n, 30))$。 ## 输出格式 一个数，即答案（对 $10^9 + 9$ 取模）。

题目描述

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 constructionManao 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 (10^{9}+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.

输入输出格式

输入格式

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

输出格式

In a single line print the remainder after dividing the number of designs by $ 1000000009 (10^{9}+9) $ .

输入输出样例

输入样例 #1

5 1

输出样例 #1

4

输入样例 #2

4 2

输出样例 #2

148

输入样例 #3

4 3

输出样例 #3

256

输入样例 #4

5 2

输出样例 #4

376

说明

Consider several designs for $ h=2 $ . A design with the first bar sticked out in direction $ d_{1} $ , the second — in direction $ d_{2} $ and so on ( $ 1<=d_{i}<=4 $ ) is denoted as string $ d_{1} $ $ d_{2} $ $ ... $ $ d_{n} $ . 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.