Marin and Anti-coprime Permutation (Codeforces 1658B)
Tags: Math, combinatorics

Marin wants you to count number of permutations that are beautiful. A beautiful permutation of length $$$n$$$ is a permutation that has the following property: $$$$$$ \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) > 1, $$$$$$ where $$$\gcd$$$ is the greatest common divisor.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).

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.Each test case consists of one line containing one integer $$$n$$$ ($$$1 \le n \le 10^3$$$).

Output: For each test case, print one integer — number of beautiful permutations. Because the answer can be very big, please print the answer modulo $$$998\,244\,353$$$.

Note: In first test case, we only have one permutation which is $$$[1]$$$ but it is not beautiful because $$$\gcd(1 \cdot 1) = 1$$$.In second test case, we only have one beautiful permutation which is $$$[2, 1]$$$ because $$$\gcd(1 \cdot 2, 2 \cdot 1) = 2$$$. 

Sample Inputs:
7
1
2
3
4
5
6
1000

Sample Outputs:
0
1
0
4
0
36
665702330

Solution (Python):
f = [1]
mod = 998244353
for i in range(1, 1001):
    f.append(f[i - 1] * i % mod)

def solve():
    n = int(input())
    if n % 2 == 1:
        return 0
    return f[n // 2] * f[n // 2] % mod
num_test = int(input())
for t in range(num_test):
    print(solve())

Solution (Python):
factorials = [1]
for i in range(1, 501):
    factorials.append(factorials[-1] * i % 998244353)
t = int(input())
for i in range(t):
    n = int(input())
    if n % 2 == 1:
        print(0)
    else:
        print(factorials[n // 2] ** 2 % 998244353)

Solution (Python):
mod = 998244353
fact = [1 for i in range(1001)]
for i in range(2, 1000 + 1):
    fact[i] = i * fact[i - 1] % mod
for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(0)
    elif n == 2:
        print(1)
    elif not n & 1:
        print(fact[n // 2] ** 2 % mod)
    else:
        print(0)