Уменьшите до одного

Рассмотрим список целых чисел $L$. Сначала $L$ содержит целые числа от $1$ до $n$, каждое ровно один раз (но позже может содержать несколько копий некоторых целых чисел). Порядок элементов в $L$ не важен. Вам следует выполнить следующую операцию $n-1$ раз:

• Выберите два элемента из списка, пусть это будут $x$ и $y$. Они могут быть равными.

• Удалите выбранные элементы из $L$.

• Добавьте число $x+y+x\cdot y$ в $L$.

В конце $L$ содержит ровно одно целое число. Найдите максимально возможное значение этого целого числа. Поскольку ответ может быть большим, вычислите его по модулю $10^9+7$.

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

Первая строка содержит количество тестов $t$. Каждая из следующих $t$ строк содержит одно целое число $n(1\le n\le 10^6)$.

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

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

Примеры