非常に大きなグラフがあり、合計で $n_1+\dots+n_k$ 個の頂点が存在します。これらを順に第 $1, 2, \dots, k$ グループと呼びます。すべての $i$ グループから $j$ グループへの頂点対について、それらの間に辺がすべて存在するか、あるいは一つも存在しないかのいずれかです。

蘭はこのグラフの全域木の数を求めたいと考え、艾鸽に尋ねました。しかし、艾鸽は期待通りに約束を破ったため、彼女はあなたに尋ねることになりました。答えを $998244353$ で割った余りを出力してください。

入力

1行目に正整数 $k$ が与えられ、グラフがいくつのグループに分かれているかを表します。

続く1行に $k$ 個の正整数 $n_1, \dots, n_k$ が与えられ、各グループの頂点数を表します。

続く $k$ 行にはそれぞれ $k$ 個の整数（$0$ または $1$）が与えられます。$a_{i,j} = 1$ は $i$ グループから $j$ グループへの頂点対の間にすべて辺が存在することを意味し、それ以外の場合は一つも存在しません。

出力

全域木の数を $998244353$ で割った余りを1行で出力してください。

入出力例

入力 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

小課題

すべてのデータにおいて、$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}$ を満たします。