Раздача подарков

Раздача подарков
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мегабайт
Скоро Новый Год! Зайчата помогли Деду Морозу упаковать все подарки для детей. Теперь настало время им самим получить подарки!
Всего Деду Морозу помогали n зайчат, пронумерованных целыми числами от 1 до n.
Дед Мороз собирается разложить вдоль волшебного коридора n подарков, также пронумерованных по порядку целыми числами от 1 до n. Чтобы получить подарки, зайчата будут по
очереди заходить в коридор. Про каждого зайчонка известно, какие из n подарков ему нравятся, а какие нет. Зайчонок прыгает вперёд до первого из оставшихся подарков, который
ему нравится, забирает его себе и идёт отдыхать. После этого в коридор заходит следующий
зайчонок.
Например, пусть n = 3, первому зайчонку нравятся все три подарка, второму — только
подарок номер 3, а третьему — подарки с номерами 1 и 2. Сначала первый зайчонок возьмёт
себе подарок номер 1. Затем второй зайчонок пропустит подарок номер 2 и возьмёт подарок
номер 3. Наконец, третий зайчонок возьмёт подарок номер 2 — ему бы понравился и подарок
номер 1, но этого подарка в коридоре уже нет.
Увы, может так случиться, что очередной зайчонок зайдёт в коридор, но ни один из
оставшихся подарков ему не понравится. Но Дед Мороз на то и волшебник, чтобы этого не
допустить!
В этом году Дед Мороз увлёкся алгеброй. Теперь, стоит лишь ему подумать про какую-то
квадратную матрицу размера n × n из нулей и единиц — и подарки окажутся такими, что:
• Если в i-й строке и j-м столбце стоит 1, то i-му зайчонку нравится j-й подарок.
• Если в i-й строке и j-м столбце стоит 0, то i-му зайчонку не нравится j-й подарок.
Квадратная матрица размера n × n из нулей и единиц называется счастливой, если в
случае, когда Дед Мороз подумает про эту матрицу, все зайчата получат подарки. Сколько
существует различных счастливых матриц? Поскольку их количество может быть очень
большим, выведите его остаток от деления на 10^9 + 7.
Формат входных данных
В единственной строке дано целое число n (1 меньше или равно n меньше или равно 105
).
Формат выходных данных
Выведите одно число — количество счастливых матриц по модулю 10^9 + 7.
Система оценки
В этой задаче 22 теста: два примера и 20 скрытых тестов. Если ваше решение проходит
оба примера, то за каждый из пройденных скрытых тестов вы получите по 5 баллов.
Гарантируется, что первые 10 скрытых тестов — это все целые числа от 3 до 12.
Примеры
стандартный ввод стандартный вывод
1 1
2 6

0