H. Thomas Sometimes Hides His Feelings in C++
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Thomas has recently begun realizing his dream of being the best mangaka in the world. He sees his future in the equation $$$E = Mc^2 + \text{AI}$$$: $$$\text{Events} = \text{Main character}^2 + \text{love}$$$.

Thomas first asks ChatGPT to generate $$$n$$$ ($$$n$$$ is even) character tropes. Then he makes a matrix $$$a$$$ of size $$$n$$$ by $$$n$$$, where $$$a_{ij}$$$ denotes the tension of someone of trope $$$i$$$ having feelings for someone of trope $$$j$$$. $$$a_{ij} = -1$$$ if the trope $$$i$$$ is unable to have any feelings for trope $$$j$$$. Note that $$$a_{ij}$$$ is not necessarily equal to $$$a_{ji} $$$.

Thomas will assign half of his $$$n$$$ tropes to male characters and the other half to female characters. He will draw feelings from each male to some female such that no two males have feelings for the same female. Then he will draw feelings from each female to each male such that no two females have feelings for the same male. Note that feelings are not necessarily reciprocated.

Note that feelings are not necessarily reciprocated. Let $$$p_i$$$ denote the trope for which the $$$i$$$-th trope has feelings. The value of this assignment (of gender and feelings) is

$$$$$$ \frac{\prod_{i \text{ is male}} a_{ip_i}}{\prod_{i \text{ is female}} a_{ip_i}}$$$$$$

Find the sum of values over all possible assignments of gender and feelings. Since this number may be very large, please find it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \text{ \lt 3}$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 21$$$, $$$n$$$ is even) — the number of tropes.

The following $$$n$$$ lines each contain $$$n$$$ integers, where the $$$j$$$-th integer of the $$$i$$$-th row is $$$a_{ij}$$$ ($$$-1 \leq a_{ij} \lt 998244353, a_{ij} \neq 0$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$50$$$ and the sum of all $$$a_ij$$$ over all test cases does not exceed lunchbox's IQ.

—

Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Test $$$1$$$ satisfies $$$n \leq 6$$$.

Test $$$2$$$ satisfies $$$n \leq 10$$$.

Tests $$$3 - 4$$$ satisfy $$$n \leq 14$$$.

Tests $$$5 - 10$$$ satisfy $$$n \leq 16$$$.

Tests $$$11 - 15$$$ satisfy $$$n \leq 18$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each test case, it can be proven that the final sum can always be expressed as $$$\frac{x}{y}$$$ for two integers $$$x$$$ and $$$y$$$. Print $$$E$$$ where $$$y \cdot E \equiv x \text{ mod } 998244353$$$ and $$$0 \leq E \lt 998244353$$$.

Examples
Input
2
2
1 1
1 1
2
1 2
1 1
Output
2
499122179
Input
2
4
1 2 -1 -1
1 1 2 -1
-1 4 1 1
-1 -1 1 1
4
1 2 3 4
5 6 7 8
10 11 12 13
14 15 16 17
Output
5
540772941
Note

In the first test case of the first sample test, Thomas has two character tropes. We will say the character trope assigned with female is Ruby and the character trope assigned with male is Aqua. Thus, the two valid assignments of $$$G$$$ and $$$p$$$ are $$$G = MF$$$, $$$p = [1, 2]$$$ with value $$$1$$$ and $$$G = FM$$$, $$$p = [1, 2]$$$ with value $$$1$$$, which sums to $$$2$$$. Either way, Ruby and Aqua have feelings for each other so everybody is happy.

In the second test case of the first sample test, there are two valid assignments of $$$G$$$ and $$$p$$$: $$$G = MF$$$, $$$p = [1, 2]$$$ with value $$$\frac{2}{1}$$$ and $$$G = FM$$$, $$$p = [1, 2]$$$ with value $$$\frac{1}{2}$$$, which sums to $$$\frac{5}{2}$$$. $$$499122179 \cdot 2 \equiv 5 \text{ mod } 998244353$$$, so we output $$$499122179$$$.

—

Problem Idea: Yam, oursaco, willy108

Problem Preparation: willy108

Problem Occurrences: Advanced H