Никогда не пейте слишком много!
Махмуд и его друзья отправились в Грузию и остановились в отеле на Руставели. Когда они прибыли, ковбои повесили свои шляпы у входа и устроились на отдых. Проходя по коридору, Махмуд заметил пивные бутылки на столе. По его предложению, все ковбои начали пить. Они выпили слишком много, и никто из них не был внимателен. Затем они решили отправиться в центр города. На выходе каждый взял шляпу, но из-за опьянения они перепутали их.
Человек, который может надеть свою собственную шляпу, будучи пьяным, считается умным, а тот, кто не может, — глупым.
Вам дано количество ковбоев — n (включая Махмуда). Необходимо определить, сколькими способами ковбои могут надеть шляпы так, чтобы все они оказались глупыми. Два способа считаются различными, если хотя бы у одного ковбоя в одном случае одна шляпа, а в другом — другая.
Так как ответ может быть очень большим, вы должны вывести результат по модулю 10^9 + 7.
Входные данные
Дано количество ковбоев — n (1 ≤ n ≤ 10^7).
Выходные данные
Выведите ответ на задачу, как указано выше.