Секретная лаборатория

На территории военной базы <<Баскервиль>> находится секретная многоэтажная лаборатория. Каждый этаж содержит ровно $n$ пронумерованых комнат. Для каждой пары комнат с номерами $i$ и $j$ существует не более одного коридора, по которому можно пройти из комнаты $i$ в комнату $j$. По каждому коридору разрешено двигатся только в одном направлении.

Этаж называется безопасным, если после выхода из любой комнаты в нее уже нельзя вернуться. Лаборатория состоит только из безопасных этажей, при этом все этажи различны. Два этажа называются различными если существуют $i$ и $j$, такие что на одном из этажей есть коридор ведущий из комнаты $i$ в комнату $j$, а на другом такого коридора нет.

Помогите Шерлоку и доктору Ватсону узнать, какое максимальное число этажей может быть в лаборатории. Из-за того, что ответ может быть очень большим, вам необходимо найти остаток от деления максимального возможного количества этажей на $10^9+7$.

Единственная строка входного файла содержит одно целое число $n$ ($1 \le n \le 6500$) --- количество комнат в этаже.

Выведите максимальное возможное количество этажей, взятое по модулю $10^9+7$.

Ниже приведены все возможные этажи из примера