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