| Codeforces Round 164 (Div. 2) |
|---|
| Закончено |
Манао работает в строительной компании. Недавно к ним пришел заказ на строительство шведских стенок в детском парке. Манао поручили разработать план постройки, который даст возможность компании максимально сэкономить средства.
Изучив формальные спецификации для шведской стенки, Манао обнаружил целый ряд неоднозначных требований и решил трактовать их в свою пользу. В итоге конструкция, в которую превратился заказ, формально описывается следующим образом:
- Введем некоторую единицу длины. Центр конструкции — шест высотой n.
- На высотах 1, 2, ..., n из шеста торчит ровно одна горизонтальная палка. Каждая палка торчит в одном из четырех заранее фиксированных направлений.
- Считается, что ребенок может перебраться от одной палки до другой, если расстояние между ними не превышает h и они торчат в одном и том же направлении. Если ребенок стоит на земле, то он может залезть на любую из палок на высоте от 1 до h. В конструкции Манао ребенок должен суметь с земли добраться до хотя бы одной из палок на высоте n - h + 1, n - h + 2, ..., n.
Слева на рисунке изображен вид обычной шведской стенки, а справа — конструкция, которую разработал Манао Манао интересует, сколько существует различных дизайнов конструкции, удовлетворяющих его требованиям. Так как это число может оказаться очень большим, найдите его остаток от деления на 1000000009 (109 + 9). Два дизайна считаются различными, если найдется такая высота i, что палки на высоте i в этих дизайнах торчат не в одном и том же направлении.
В единственной строке записаны через пробел два целых числа n и h (1 ≤ n ≤ 1000, 1 ≤ h ≤ min(30, n)).
В единственной строке выведите остаток от деления количества дизайнов на 1000000009 (109 + 9).
5 1
4
4 2
148
4 3
256
5 2
376
Рассмотрим несколько дизайнов при h = 2. Дизайн, в котором первая палка торчит в направлении d1, вторая — в направлении d2 и так далее (1 ≤ di ≤ 4), будем обозначать строкой d1d2...dn.
Дизайн «1231» (первые три палки торчат в разных направлениях, последняя — в том же, что и первая). Ни до палки на высоте 3, ни до палки на высоте 4 ребенок добраться не может.
Дизайн «414141». Ребенок может добраться до палки на высоте 5, взобравшись изначально на первую палку, с нее — на третью и с третьей на пятую. Также он может добраться до палки на высоте 6 по маршруту: вторая → четвертая → шестая палки.
Дизайн «123333». До верхних двух палок добраться невозможно.
Дизайн «323323». Можно добраться до палки на высоте 6 по маршруту: первая → третья → четвертая → шестая палки.
