← 返回题目列表

Codeforces · 268/D

D. 墙条

中文机器翻译题面 查看原题

Manao 在一家建筑公司工作。最近,接到一份在儿童公园建造墙吧的订单。 Manao 受委托制定一项施工计划,这将使公司节省最多的资金。

在审查了墙筋的正式规格后,Manao 发现了一些有争议的要求,并决定根据公司的利益来对待它们。他的最终设计可以描述如下:

- 让我们介绍一些长度单位。构造中心是一根高为n的柱子。
- 在高度 1、 2、 ...、 n 处,恰好有一根单杠从杆子中伸出。每个棒都粘在四个预先固定的方向之一。
- 如果孩子之间的距离不超过 h 并且沿相同方向粘着,则孩子可以从一个栏移动到另一栏。如果孩子在地面上,他可以爬上任何高度在 1 到 h 之间的栏杆。在马瑙的构造中,如果孩子从地面开始,他应该能够至少到达高度为 n - h + 1, n - h + 2, ..., n 的杆子。

左图显示了一组常见的墙栏的外观。右图为Manao的构造

Manao 想知道有多少种不同的建筑设计可以满足他的要求。由于该数字可能相当大,因此请打印除以 1000000009 (109 + 9) 后的余数。如果两个设计的高度 i 一致,且这些设计中高度 i 上的条形不向同一方向伸出,则认为这两个设计是不同的。

输入

单行包含两个空格分隔的整数 n 和 h (1 ≤ n ≤ 1000, 1 ≤ h ≤ min(n, 30))。

输出

在一行中打印设计数除以 1000000009 (109 + 9) 后的余数。

示例

输入 #1

5 1

输出 #1

4

输入 #2

4 2

输出 #2

148

输入 #3

4 3

输出 #3

256

输入#4

5 2

输出#4

376

注意

考虑 h​​ = 2 的几种设计。第一个条沿方向 d1 伸出,第二个条沿方向 d2 伸出,依此类推 (1 ≤ di ≤ 4) 的设计表示为字符串 d1d2...dn。

设计“1231”(前三个条向不同方向伸出,最后一个与第一个条相同)。儿童既无法够到高度为 3 的杠铃,也够不到高度为 4 的杠铃。

设计“414141”。孩子可以到达高度为 5 的栏杆。为此,他应该首先攀爬第一个栏杆,然后攀爬第三个栏杆,最后攀爬第五个栏杆。他还可以通过第二小节 → 第四小节 → 第六小节的路线到达高度 6 处的小节。

设计“123333”。孩子够不到上面的两根横杆。

设计“323323”。高度为 6 的栏可通过以下路线到达:第一栏 → 第三栏 → 第四栏 → 第六栏。