B. Морднилап
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$). Всего существует $$$n! = n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1$$$ различных перестановок длины $$$n$$$.

По произвольной перестановке $$$p$$$ длины $$$n$$$ мы создаем массив $$$a$$$ длины $$$2n$$$, который равен конкатенации $$$p$$$ и ее разворота. Далее, стоимостью $$$p$$$ назовем число инверсий в $$$a$$$.

Число инверсий в массиве $$$a$$$ определяется как количество пар индексов $$$i$$$, $$$j$$$, таких что $$$i < j$$$ и $$$a_i > a_j$$$.

Например, если $$$p = [1, 2]$$$, то $$$a$$$ будет равно $$$[1, 2, 2, 1]$$$. В $$$a$$$ всего две инверсии: $$$(2, 4)$$$ и $$$(3, 4)$$$ (нумерация элементов с 1). Значит, стоимость $$$p$$$ равна $$$2$$$.

Ваша задача — найти сумму стоимостей всех $$$n!$$$ перестановок длины $$$n$$$. Выведите остаток от деления этой суммы на $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит число $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — сумму стоимостей всех перестановок длины $$$n$$$ по модулю $$$1\,000\,000\,007$$$ ($$$10^9 + 7$$$).

Пример
Входные данные
3
1
2
100
Выходные данные
0
4
389456655
Примечание

В первом наборе входных данных $$$p = [1]$$$ — единственная возможная перестановка. Тогда $$$a = [1, 1]$$$, и в этом массиве $$$0$$$ инверсий.

Во втором наборе входных данных перестановки — это $$$[1, 2]$$$ и $$$[2, 1]$$$. Их соответствующие массивы $$$a$$$ таковы: $$$[1, 2, 2, 1]$$$ и $$$[2, 1, 1, 2]$$$. В них обоих по $$$2$$$ инверсии.