CF268D.Wall Bars

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.

马瑙就职于一家建筑公司。最近，公司接到一项在儿童公园建造攀爬墙栏的订单。马瑙受命制定施工方案，以帮助公司节省最多的资金。

在审阅了攀爬墙栏的正式技术规范后，马瑙发现其中存在若干有争议的要求，于是决定利用这些要求为公司谋取优势。他最终的设计方案可描述如下：

• 引入一个长度单位。施工中心是一根高度为 $n$ 的竖直杆。
• 在高度 $1,\,2,\,\dots,\,n$ 处，恰好各有一根水平横杆从竖直杆上伸出。每根横杆均朝向四个预先固定的方向之一伸出。
• 若两根横杆之间的垂直距离不超过 $h$，且它们朝向相同，则儿童可以从一根横杆移动到另一根横杆。若儿童站在地面上，他可以攀爬上任意一根高度位于 $1$ 到 $h$（含端点）之间的横杆。在马瑙的设计中，儿童必须能够从地面出发，至少抵达高度为 $n-h+1,\,n-h+2,\,\dots,\,n$ 中的某一根横杆。

左图展示了一组常见的攀爬墙栏；右图展示了马瑙的设计方案。

马瑙想知道：满足上述要求的不同设计方案共有多少种？由于该数目可能非常大，请输出其对 $1000000009$（即 $10^9 + 9$）取模的结果。若存在某个高度 $i$，使得两个设计方案在该高度处的横杆朝向不同，则认为这两个设计方案互不相同。

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

一行包含两个用空格分隔的整数 $n$ 和 $h$（$1 \le n \le 1000$，$1 \le h \le \min(n, 30)$）。

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

在一行中输出设计方案数对 1000000009（$10^9 + 9$）取模后的余数。

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.

考虑若干种 $ h = 2 $ 的设计方案。若第 $1$ 根横杆朝方向 $ d_1 $ 伸出，第 $2$ 根横杆朝方向 $ d_2 $ 伸出，依此类推（其中 $ 1 \le d_i \le 4 $），则该设计方案记为字符串 $ d_1d_2\ldots d_n $。

设计方案 “1231”（前三根横杆分别朝不同方向伸出，最后一根与第一根方向相同）。儿童既无法到达高度为 $3$ 的横杆，也无法到达高度为 $4$ 的横杆。

设计方案 “414141”。儿童可以到达高度为 $5$ 的横杆。为此，他应先攀爬第 $1$ 根横杆，再攀爬第 $3$ 根横杆，最后攀爬第 $5$ 根横杆。他也可以通过路径：第 $2$ 根 → 第 $4$ 根 → 第 $6$ 根横杆，到达高度为 $6$ 的横杆。

设计方案 “123333”。儿童无法到达最上面的两根横杆。

设计方案 “323323”。高度为 $6$ 的横杆可通过如下路径到达：第 $1$ 根 → 第 $3$ 根 → 第 $4$ 根 → 第 $6$ 根横杆。