There is a large graph with a total of $n_1 + \dots + n_k$ nodes, which we refer to as parts $1, 2, \dots, k$. For all pairs of nodes between part $i$ and part $j$, either all edges exist or no edges exist.
Lan wants to know how many spanning trees this graph has, so she asks Aige. However, as expected, Aige flakes on her, so she has to ask you instead. You only need to output the answer modulo $998244353$.
Input
The first line contains a positive integer $k$, representing the number of parts in the graph.
The next line contains $k$ positive integers $n_1, \dots, n_k$, representing the number of nodes in each part.
The next $k$ lines each contain $k$ integers, either $0$ or $1$, where $a_{i,j} = 1$ means that all edges between part $i$ and part $j$ exist, and otherwise, no edges exist.
Output
Output a single integer representing the number of spanning trees, modulo $998244353$.
Subtasks
For $100\%$ of the data, it is guaranteed that $1 \le k \le 300$, $1 \le n_i \le 10^8$, $0 \le a_{i,j} \le 1$, and $a_{i,j} = a_{j,i}$.
| Test Case | Special Constraints |
|---|---|
| $1$ | The graph is a complete graph |
| $2$ | The graph is a complete bipartite graph |
| $3$ | $k=2$ |
| $4$ | $k=3$ |
| $5$ | $a_{i,j}=[i\neq j], n_i=n_j$ |
| $6,7$ | $n_i = 1$ |
| $8$ | $k \le 9$ |
| $9,10$ | None |
Examples
Input 1
2 2 2 1 1 1 0
Output 1
8
Input 2
4 12 34 56 78 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
Output 2
353527476