For an undirected graph $G = (V, E)$, the Tutte polynomial can be defined as $T_G(x,y)=\sum_{A\subseteq E}(x-1)^{k(A)-k(E)}(y-1)^{k(A)+|A|-|V|}$, where $k(E)$ denotes the number of connected components of the graph $(V, E)$. It has several other definitions that appear more concise and natural, as well as many excellent properties, but for this problem, only this definition is needed.

For certain $(x, y)$, the Tutte polynomial is related to various counting problems. The Tutte polynomial of a graph is equal to the product of the Tutte polynomials of its connected components; for convenience, we assume below that the graph $G$ is connected.

It is easy to observe that $T_G(1, 1)$ is the number of spanning trees (i.e., acyclic connected spanning subgraphs) of $G$, $T_G(2, 1)$ is the number of spanning forests (i.e., acyclic spanning subgraphs) of $G$, $T_G(1, 2)$ is the number of connected spanning subgraphs of $G$, and $T_G(2, 2)$ is the number of spanning subgraphs of $G$, which is $2^{|E|}$.

When $y=0$, we have $P_G(k)=(-1)^{|V|-k(E)}\;\; k^{k(E)} T_G(1-k, 0)$, where $P_G(k)$ denotes the chromatic polynomial of $G$, which is the number of $k$-colorings of the vertices of $G$.

• In particular, $T_G(2, 0)$ is the number of acyclic orientations of $G$.

When $x=0$, we have $C_G(k)=(-1)^{|E|-|V|+k(E)}\;\;T_G(0, 1-k)$, where $C_G(k)$ denotes the flow polynomial of $G$, which is the number of nowhere-zero $k$-flows of $G$.

• In particular, $T_G(0, 2)$ is the number of strong orientations of $G$.

For a graph $G=(V, E)=(\{0, 1, \ldots, n-1\}, E)$ without multiple edges or self-loops, compute $T_G(x, y) \bmod 998244353$.

Input

Line 1: $n$

Line $2+i$ ($0 \leq i \leq n-1$): $G_{i, 0}\ G_{i, 1}\ \ldots G_{i, n-1}$, where $G_{i, j} = 0$ means $(i, j) \notin E$ and $G_{i, j} = 1$ means $(i, j) \in E$

Line $2+n$: $x\ y$

Output

Line 1: $T_G(x, y) \bmod 998244353$

Examples

Input 1

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]

Output 1

(0, 1): 6
(0, 2): 24
(1, 0): 10
(1, 1): 24
(1, 2): 52
(2, 0): 60
(2, 1): 86

Note

[x] and [y] are the input $x$ and $y$. The sample output provides the results for several possible $(x, y)$ pairs.

Constraints

• $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$

Subtasks

1. (16 points) $n \leq 7$
2. (20 points) $n \leq 11$
3. (14 points) $n \leq 14$
4. (25 points) $n \leq 18$
5. (25 points) No additional constraints