Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Обмен

(Время: 1 сек. Память: 16 Мб Сложность: 50%)

Как вы знаете, самый известный коллекционер фантиков в мире – это смешарик по имени Ежик. Но просто коллекционировать фантики ему не интересно, главное здесь – это обмен. Для обмена фантиками со своими друзьями Ежик придумал следующий способ: был составлен список, кто из смешариков кому отдает свои фантики. Каждый смешарик отдавал свои фантики только одному конкретному смешарику и получал фантики тоже только от одного конкретного смешарика. По правилам Ежика, фантики можно получать от того же смешарика, которому они отдаются.

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

Входные данные

Входной файл INPUT.TXT содержит целое число N – количество смешариков, задействованных в обмене (2 ≤ N ≤ 105).

Выходные данные

В выходной файл OUTPUT.TXT выведите количество вариантов обмена фантиками по модулю 109+9.

Примеры

INPUT.TXTOUTPUT.TXT
121
232
349

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Формулы
 Динамика
 Перебор
 A. Хоккей
 B. Салаты
 C. Шахматы - 2
 D. Карточки
 E. Обмен
 F. Волейбол
 G. Волейбол - 2
 H. Великий комбинатор
 I. День рождения
 J. Нолики

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483