Codeforces Round 745 (Div. 2) |
---|
Закончено |
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$$$. Например:
CQXYM хочет, чтобы вы помогли ему найти количество таких перестановок по модулю $$$1000000007$$$($$$10^9+7$$$).
Операцией по модулю называется взятие остатка от деления. Например:
Входные данные состоят из нескольких тестовых примеров.
Первая строка содержит целое число $$$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].$$$
Название |
---|