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

CQXYM считает перестановки длины $$$2n$$$.

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

Перестановка $$$p$$$(длины $$$2n$$$) будет посчитана только в том случае, если количество $$$i$$$, удовлетворяющих $$$p_i<p_{i+1}$$$, не меньше $$$n$$$. Например:

  • Перестановка $$$[1, 2, 3, 4]$$$ будет посчитана, так как количество таких $$$i$$$ что $$$p_i<p_{i+1}$$$ равно $$$3$$$ ($$$i = 1$$$, $$$i = 2$$$, $$$i = 3$$$).
  • Перестановка $$$[3, 2, 1, 4]$$$ не будет посчитана, так как количество таких $$$i$$$ что $$$p_i<p_{i+1}$$$ равно $$$1$$$ ($$$i = 3$$$).

CQXYM хочет, чтобы вы помогли ему найти количество таких перестановок по модулю $$$1000000007$$$($$$10^9+7$$$).

Операцией по модулю называется взятие остатка от деления. Например:

  • $$$7 \mod 3=1$$$, так как $$$7 = 3 \cdot 2 + 1$$$,
  • $$$15 \mod 4=3$$$, так как $$$15 = 4 \cdot 3 + 3$$$.
Входные данные

Входные данные состоят из нескольких тестовых примеров.

Первая строка содержит целое число $$$t (t \geq 1)$$$ — количество тестовых примеров. Ниже приводится описание тестовых случаев.

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

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

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

Для каждого примера выведите ответ в отдельной строке.

Пример
Входные данные
4
1
2
9
91234
Выходные данные
1
12
830455698
890287984
Примечание

$$$n=1$$$, существует только одна перестановка, удовлетворяющая условию: $$$[1,2].$$$

В перестановке $$$[1,2]$$$, $$$p_1<p_2$$$, только $$$i=1$$$ подходит под условие. Так как $$$1 \geq n$$$, Эта перестановка будет посчитана. В перестановке $$$[2,1]$$$, $$$p_1>p_2$$$. Так как $$$0<n$$$, эта перестановка не будет посчитана.

$$$n=2$$$, существует $$$12$$$ перестановок: $$$[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,1,3],[3,1,2,4],[3,4,1,2],[4,1,2,3].$$$