Мадока уже закончила писать муниципальный этап в Новосибирске и пошла домой ждать результатов закрытого тестирования.

На олимпиаде была ровно одна задача — дана перестановка чисел от $$$1$$$ до $$$n$$$: $$$p_1, p_2, \ldots, p_n$$$. Нужно узнать, какое минимальное раз можно поменять местами соседние элементы, чтобы перестановка стала отсортированной в порядке возрастания.

Но Мадока решила её следующим образом: $$$k + \frac{|1 - p_1| + |2 - p_2| + \ldots + |n - p_n|}{2}$$$. Так как жюри знает, кто отец Мадоки, то, чтобы не потерять работу, они должны сделать такие тесты, чтобы решение Мадоки было верным. И поэтому им стало интересно, сколько существует перестановок длины $$$n$$$, для которых решение Мадоки выведет верный ответ на задачу, но так как ответ на задачу может быть слишком большим, то выведите его по модулю $$$10^9 + 7$$$.