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 的栏可通过以下路线到达:第一栏 → 第三栏 → 第四栏 → 第六栏。