Consider two binary arrays A and B, each of size N and a permutation^\dagger P of length N. 

You will make two new arrays C and D, each of size N, such that:

C_{i}=A_{P_{i}}  (1 ≤ i ≤ N)
D_{i}=B_{P_{i}}  (1 ≤ i ≤ N)

Let us define:
The score of the permutation P as \min(\text{LNDS}(C),\text{LNDS}(D)), where \text{LNDS}(X) gives the length of longest non-decreasing subsequence^{\ddagger} of X. 
F(A,B) as the maximum score over all possible N! permutations P.

Find \sum_{x \in S} \sum_{y \in S}{F(x,y)}, where S contains all binary arrays of size N(|S|=2^{N}).

Since sum might be large, please print it modulo 998244353.

^\dagger A permutation of length N consists of all integers from 1 to N exactly once. For example, [4,2,3,1] is a permutation, while [1,2,2] is not a permutation.

^{\ddagger} A sequence A is a subsequence of a sequence B if A can be obtained from B by deletion of several (possibly, zero or all) elements. For example, [3,1] is a subsequence of [3,2,1], [4,3,1] and [3,1], but not [1,3,3,7] and [3,10,4].

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The only line of each test case contains a single integer N, where N should be the length of the binary arrays.

------ Output Format ------ 

For each test case, output on a new line, the sum modulo 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2000$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{3}$.

----- Sample Input 1 ------ 
5
1
2
3
4
343

----- Sample Output 1 ------ 
4
30
174
914
857794275

----- explanation 1 ------ 
Test case $1$: 
$\\ 
F(0,0) = 1 \\
F(0,1) = 1 \\
F(1,0) = 1 \\
F(1,1) = 1$

Test case $2$: $S=[00,01,10,11]$. So we have $16$ pairs of $(x,y)$.

$F(00,00) = 2 \\
F(00,10) = 2 \\
F(00,01) = 2 \\
F(00,11) = 2 \\
F(10,00) = 2 \\
F(10,10) = 2 \\
F(10,01) = 1 \\
F(10,11) = 2 \\
F(01,00) = 2 \\
F(01,10) = 1 \\
F(01,01) = 2 \\
F(01,11) = 2 \\
F(11,00) = 2 \\
F(11,10) = 2 \\
F(11,01) = 2 \\
F(11,11) = 2$

To get maximum score for pair $(11,10)$, we can take $P=[2,1]$.

Now $C=[1,1]$ and $D=[0,1]$. Thus, maximum score is $2$.

Test case $3$: $S = [000, 001, 010, 011, 100, 101, 110, 111]$.

Consider $A = 001, B = 110,$ and a random $P = [2, 3, 1]$. Thus, $C$ and $D$ can be generated as :
- $C = A_{P_{1}}A_{P_{2}}A_{P_{3}} = A_{2A}_3A_{1} = 010$.  
The longest non-decreasing subsequence are $00$ or $01$, each having length $2$.
- $D = B_{P_{1}}B_{P_{2}}B_{P_{3}} = B_{2B}_3B_{1} = 101$.  
The longest non-decreasing subsequence is $01$, having length $2$.

Thus, score of $P = [2, 3, 1]$ is $2$ over $A = 001$ and $B = 110$. Similarly, we find the sores of all permutations of length $3$ over $A$ and $B$ and set $F(A, B)$ as maximum out of those.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
mod = 998244353
maxN = 2005
C = [[0 for _ in range(maxN)] for _ in range(maxN)]
for i in range(maxN):
	C[i][0] = 1
	for j in range(1, i + 1):
		C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod
sumn = 0
for i in range(int(input())):
	n = int(input())
	ans = 0
	for same in range(n + 1):
		dif = n - same
		ways = C[n][same] * pow(2, same, mod) % mod
		for x in range(dif + 1):
			y = dif - x
			ans += (same + max(x, y) + min(x, y) // 2) * C[dif][x] * ways
			ans %= mod
	sumn += n
	print(ans)