Codeforces Beta Round 15 |
---|
Закончено |
Летом Петя отдыхал у бабушки в селе, когда неподалеку на овец напал волк. Теперь Петя боится ходить через лес, боится обходить лес, боится даже выходить из дому. Объясняет свой страх Петя отнюдь не боязнью волка, а непонятным, на его взгляд, строением леса, который имеет n уровней, где n — четное число.
В местном муниципалитете Вам предоставили карту местности, на которой бабушкин домик отмечен точкой H, а участки леса выделены заливкой серого цвета (см. рисунок для понимания того, как устроена местность).
Но все же, после долгого сидения дома, Петя решил поддаться на уговоры бабушки и пойти подышать свежим воздухом. Как человек предусмотрительный, Петя заранее планирует прогулку, и ему необходимо выбрать маршрут. Маршрут, который Петя считает приемлемым для себя, обладает следующими свойствами:
Необходимо посчитать количество таких приемлемых ориентированных маршрутов по модулю 1000000009.
На рисунке представлен пример карты местности для n = 12. Так как карта имеет регулярную структуру, для других значений n ее можно построить самостоятельно по аналогии.
Входные данные содержат единственное целое четное число n (2 ≤ n ≤ 106).
Выведите единственное число — количество путей Пети по модулю 1000000009.
2
10
4
74
Название |
---|