Обмен

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

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

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

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

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

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

Примеры

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