CQXYM Count Permutations (Codeforces 1581A)
Tags: Math, combinatorics

CQXYM is counting permutations length of $$$2n$$$.A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).A permutation $$$p$$$(length of $$$2n$$$) will be counted only if the number of $$$i$$$ satisfying $$$p_i<p_{i+1}$$$ is no less than $$$n$$$. For example:  Permutation $$$[1, 2, 3, 4]$$$ will count, because the number of such $$$i$$$ that $$$p_i<p_{i+1}$$$ equals $$$3$$$ ($$$i = 1$$$, $$$i = 2$$$, $$$i = 3$$$). Permutation $$$[3, 2, 1, 4]$$$ won't count, because the number of such $$$i$$$ that $$$p_i<p_{i+1}$$$ equals $$$1$$$ ($$$i = 3$$$). CQXYM wants you to help him to count the number of such permutations modulo $$$1000000007$$$ ($$$10^9+7$$$).In addition, modulo operation is to get the remainder. For example:  $$$7 \mod 3=1$$$, because $$$7 = 3 \cdot 2 + 1$$$,  $$$15 \mod 4=3$$$, because $$$15 = 4 \cdot 3 + 3$$$. 

Input: The input consists of multiple test cases. The first line contains an integer $$$t (t \geq 1)$$$ — the number of test cases. The description of the test cases follows.Only one line of each test case contains an integer $$$n(1 \leq n \leq 10^5)$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$

Output: For each test case, print the answer in a single line.

Note: $$$n=1$$$, there is only one permutation that satisfies the condition: $$$[1,2].$$$In permutation $$$[1,2]$$$, $$$p_1<p_2$$$, and there is one $$$i=1$$$ satisfy the condition. Since $$$1 \geq n$$$, this permutation should be counted. In permutation $$$[2,1]$$$, $$$p_1>p_2$$$. Because $$$0<n$$$, this permutation should not be counted.$$$n=2$$$, there are $$$12$$$ permutations: $$$[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].$$$

Sample Inputs:
4
1
2
9
91234

Sample Outputs:
1
12
830455698
890287984

Solution (Python):
t = int(input())
for _ in range(t):
    n = 2 * int(input())
    c = 1
    for i in range(1, n + 1):
        c = c * i % 1000000007
    print((c + 1000000007) // 2 if c % 2 else c // 2)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(1)
    else:
        a = 1
        for i in range(3, 2 * n + 1):
            a *= i
            a %= 1000000007
        print(a)

Solution (Python):
dp = [1] * 100001

def dp_filling():
    for i in range(2, 100001):
        dp[i] = (i * 2 - 1) * dp[i - 1] % 1000000007 * (i * 2) % 1000000007

def solve():
    print(dp[int(input())])
if __name__ == '__main__':
    dp_filling()
    for test in range(int(input())):
        solve()