Задача 20. Смутный сон ≡

Условие

...

София

Я гнева вашего никак не растолкую.

Он в доме здесь живет, великая напасть!

Шел в комнату, попал в другую.

Фамусов

Попал или хотел попасть?

...

София

По смутном сне безделица тревожит;

Сказать вам сон: поймете вы тогда.

Фамусов

Что за история?

София

Вам рассказать?

Фамусов

Ну да.

...

Александр Грибоедов, "Горе от ума", 1824 г.

Автору этой задачи в детстве часто снился один и тот же странный сон: будто возвращаюсь я с прогулки домой, захожу в родной подъезд и обнаруживаю, что все квартиры в доме перепутаны. Причем поменялись не просто номерки на дверях, а сами квартиры "переехали" на новое место, например там, где на первом этаже жили мои друзья Сашка с Сережкой теперь находится совершенно чужая квартира из другого подъезда. Я стою в полной растерянности и не знаю, что же мне делать и где искать свою квартиру.

Бог сна Гипнос готовит для Антона очередное сновидение. Его цель — так переставить все n квартир, расположенных в доме Антона, чтобы ни одна из них не осталась на своём исходном месте. Сколько у него есть способов это сделать?

Формат входных данных

Единственная строка входного файла содержит натуральное число n — количество квартир в доме.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 20

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере дано n = 3. Существует шесть перестановок чисел от 1 до 3: 123, 132, 213, 231, 312, 321.

Из них Гипносу подходят только две: 231 и 312.

Примеры тестов

3

2