eolymp
bolt
Try our new interface for solving problems
Məsələlər

Олимпийская система

Олимпийская система

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Двое руководителей организуют соревнования среди N команд по олимпийской системе. Все команды перенумерованы числами от 1 до N. Наши руководители очень занятые люди. Поэтому они определяют только кому проводить очередной матч, выбирая каждый раз команды с соседними номерами. Все остальное делают их ассистенты. После завершения матча проигравший выбывает, а еще не выбывшие команды, имеющие более высокие номера (если таковые есть), сдвигаются на 1 номер вперед (т.е. уменьшают свои номера на 1) и руководитель (тот, который в этот момент более свободен) приглашается для выбора очередной пары команд (одновременно оба руководителя свободными быть не могут). Соревнования заканчиваются, когда остается только одна команда. Решениям руководителей можем поставить в соответствие последовательность чисел, полученную выписыванием меньших номеров команд для каждой пары, выбранной руководителем.

Например, если команд было 4, а соперничающие пары выбирались в следующем порядке: (1, 2), (2, 3), (1, 2), то получаем последовательность 1, 2, 1. Заметим, что некоторые последовательности определяют одинаковые пары соперничающих команд, отличающиеся только порядком проведения матчей. Такие последовательности будем называть эквивалентнными.

Например, приведенная выше последовательность эквивалентна последовательности 3, 1, 1. Действительно, в терминах исходных номеров, в первом случае, вначале встречаются команды 1, 2, затем 3, 4, а затем победители этих пар встречаются между собой. Во втором случае, наоборот, вначале встречаются 3, 4, затем 1, 2, после чего победители пар встречаются друг с другом.

Для заданного N определить максимальное количество последовательнстей, которые можно получить вышеописанным образом, среди которых нет ни одной пары эквивалентных.

Giriş verilənləri

В первой строке число N (1N1000000).

Çıxış verilənləri

В единственной строке – ответ задачи. Ответ выдать по модулю 1000000009 (10^9+9).

Nümunə

Giriş verilənləri #1
1 
Çıxış verilənləri #1
1