矩阵的 Hafnian

【题目描述】

给定 $N \times N$ 的对角线全为 $0$ 的对称矩阵 $A = (a_{i,j})$。输出 $A$ 的 Hafnian 对 $998244353$ 取模的结果。

【输入】

$N$
$a_{0,0}$ $a_{0,1}$ $\ldots$ $a_{0,N-1}$
$a_{1,0}$ $a_{1,1}$ $\ldots$ $a_{1,N-1}$
$\vdots$
$a_{N-1,0}$ $a_{N-1,1}$ $\ldots$ $a_{N-1,N-1}$

【输出】

输出 $A$ 的 Hafnian 对 $998244353$ 取模的结果。

【输入样例】

4
0 1 2 4
1 0 3 5
2 3 0 6
4 5 6 0

【输出样例】

28

【数据范围】

• $2 \le N \le 38$
• $N \bmod 2 = 0$
• $0 \le a_{ij} \lt 998244353$
• $a_{i,i} = 0$
• $a_{i,j} = a_{j,i}$

【来源】

Library Checker（yosupo06） hafnian_of_matrix