155 Tutte 多项式

这是一道（集合幂级数对数和指数、所有点子集生成树计数以及一些其他东西的）模板题。

对于一个无向图 $G = (V, E)$，Tutte 多项式可以定义为 $T_G(x,y)=\sum_{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}$，其中 $k(E)$ 表示图 $(V, E)$ 的连通分量数。它还有一些看起来更简洁自然的定义和很多优秀的性质，但在这题只需要知道这个定义。

在一些 $(x, y)$ 上，Tutte 多项式和一些计数问题相关。一个图的 Tutte 多项式等于它的所有连通分量的 Tutte 多项式之积，为了方便，以下假设图 $G$ 连通。

• 容易观察到 $T_G(1, 1)$ 是 $G$ 的生成树（即无环连通生成子图）数量，$T_G(2, 1)$ 是 $G$ 的生成森林（即无环生成子图）数量，$T_G(1, 2)$ 为 $G$ 的连通生成子图数量，$T_G(2, 2)$ 是 $G$ 的生成子图数量，即 $2^{|E|}$。
• $y=0$ 时有 $P_G(k)=(-1)^{|V|-k(E)}k^{k(E)}T_G(1-k, 0)$，$P_G(k)$ 表示 $G$ 的色多项式，是 $G$ 的顶点 $k$ 染色的数量。
• 特别地，$T_G(2, 0)$ 是 $G$ 的无环定向数量。
• $x=0$ 时有 $C_G(k)=(-1)^{|E|-|V|+k(E)}T_G(0, 1-k)$，$C_G(k)$ 表示 $G$ 的流多项式，是 $G$ 的无处为零 $k$-流的数量。
• 特别地，$T_G(0, 2)$ 是 $G$ 的强连通定向数量。

对一个无重边无自环的图 $G=(V, E)=({0, 1, \ldots, n-1}, E)$，求 $T_G(x, y) \bmod 998244353$。

第 $1$ 行：$n$

第 $2+i$ 行（$0 \leq i \leq n−1$）：$G_{i, 0}\ G_{i, 1}\ \ldots G_{i, n-1}$，$G_{i, j}$ 为 $0$ 表示 $(i, j) \notin E$ ，为 $1$ 表示 $(i, j) \in E$

第 $2+n$ 行：$x\ y$

第 $1$ 行：$T_G(x, y) \bmod 998244353$

样例输入

5
0 1 1 0 1
1 0 0 1 1
1 0 0 1 1
0 1 1 0 0
1 1 1 0 0
[x] [y]

[x] 和 [y] 是输入的 $x$ 和 $y$，样例输出中给出了一些可能的 $(x, y)$ 对应的输出。

样例输出

• $1 \leq n \leq 21$
• $G_{i, j} \in {0, 1}, G_{i, j} = G_{j, i}, G_{i, i} = 0$
• $0 \leq x, y < 998244353$

子任务

1. （16 分）$n \leq 7$
2. （20 分）$n \leq 11$
3. （14 分）$n \leq 14$
4. （25 分）$n \leq 18$
5. （25 分）没有附加限制