现在有一张很大的图，总共有 $n_1+\dots+n_k$ 个节点，我们依次称其为第 $1,2,\dots,k$ 部分。对于全体 $i$ 部分到 $j$ 部分的点对，要么全都有边，要么全都没有边。
兰想知道这张图有多少颗生成树，于是去问艾鸽。但艾鸽不出所望地鸽了，于是她只能问你了。你只需要输出答案同余 $998244353$ 的结果。
输入格式
第一行输入一个正整数 $k$，表示图分为几个部分。
接下来一行输入 $k$ 个正整数 $n_1,\dots,n_k$，表示各部分的点数。
接下来 $k$ 行每行输入 $k$ 个整数，为 $0$ 或 $1$，其中 $a_{i,j} =1$ 表示 $i$ 部分到 $j$ 部分的点对全都有边，否则全都没有。
输出格式
输出一行一个整数，表示生成树数量，同余 $998244353$。
样例数据
样例 1 输入
2 2 2 1 1 1 0
样例 1 输出
8
样例 2 输入
4 12 34 56 78 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
样例 2 输出
353527476
子任务
对于 $100\%$ 的数据，保证 $1\le k\le 300, 1\le n_i \le 10^8, 0\le a_{i,j}\le 1, a_{i,j} = a_{j,i}$。
| 测试点 | 特殊限制 |
|---|---|
| $1$ | 图构成完全图 |
| $2$ | 图构成完全二分图 |
| $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$ | 无 |