现在有一张很大的图，总共有 $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}$。