Олімпійська система
Двоє керівників організовують змагання серед 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 визначте максимальну кількість послідовностей, які можна отримати вищеописаним чином, серед яких немає жодної пари еквівалентних.
Вхідні дані
У першому рядку число N (1 ≤ N ≤ 1000000).
Вихідні дані
В єдиному рядку — відповідь задачі. Відповідь подати за модулем 1000000009 (10^9+9).