「松活弾抖閃電鞭」を極めるには、まず三次元立体混元勁を習得しなければならない。

馬先生は高次元太極拳の達人である。彼が $k$ 次元空間で拳法を教えた経験に基づくと、君は $k$ 次元の生物であり、体には $n_1+\dots+n_k$ 個のツボがある。そのうち $n_j$ 個のツボは第 $j$ 次元に属している。$k$ 次元立体混元勁を習得するには、経絡を通す必要がある。つまり、これら $n_1+\dots+n_k$ 個のツボをすべて経絡で連結しなければならない。ツボを頂点、経絡を辺とみなすと、これらは連結グラフを構成する必要がある。第 $i$ 次元にあるツボと第 $j$ 次元にあるツボの間には、$a_{i,j}$ 通りの経絡の通し方があることがわかっている。なお、同じ次元にあるツボ同士も連結可能であるが、自分自身と連結することはできない。

経絡を通す方法が何通りあるか計算せよ。答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを求めよ。

入力

入力は以下の形式で与えられる。

$k$ $n_1 \ n_2 \ \dots \ n_k$ $a_{1,1} \ a_{1,2} \ \dots \ a_{1,k}$ $a_{2,1} \ a_{2,2} \ \dots \ a_{2,k}$ $\vdots$ $a_{k,1} \ a_{k,2} \ \dots \ a_{k,k}$

第1行には、空間の次元を表す正整数 $k$ が与えられる。

第2行には、$k$ 個の正整数が与えられる。第 $j$ 番目の数は $n_j$、すなわち第 $j$ 次元におけるツボの数を表す。

続く $k$ 行には、$k$ 個ずつの整数が与えられる。第 $i$ 行第 $j$ 列の数は $a_{i,j}$ を表す。ただし、$a_{i,j}=a_{j,i}$ が保証される。

出力

経絡を通す方法の総数を $998244353$ で割った余りを1行で出力せよ。

入出力例

入力 1

2
2 1
1 2
2 1

出力 1

12

注記 1

合計 $2+1=3$ 個のノードがある。$(1,2)$ 間には $1$ 通りの連結方法があり、$(1,3)$ および $(2,3)$ 間にはそれぞれ $2$ 通りの連結方法がある。

$(1,2)$ 間を連結した場合、残りの連結方法は $(2+1)^2-1=8$ 通りである。

$(1,2)$ 間を連結しなかった場合、$(1,3)$ と $(2,3)$ はそれぞれ連結しなければならず、$2\times 2 = 4$ 通りとなる。

合計で $8+4=12$ 通りである。

入力 2

2
7 4
1 998244352
998244352 0

出力 2

188336

制約

$N=(n_1+1)\times \dots \times(n_k+1)$ とする。

すべてのデータにおいて、$N\le 2.5\times 10^5, 0\le a_{i,j} < 998244353$ を満たす。