要想打好松活彈抖閃電鞭，就得先掌握三維立體混元勁。

馬老師是一名高維太極武術大師，根據他在 $k$ 維空間教人打拳的經歷，他指出，你作為一名 $k$ 維生物，身上有 $n_1+\dots+n_k$ 處穴位，其中有 $n_j$ 處穴位來自第 $j$ 個維度。要想練好 $k$ 維立體混元勁，必先打通經脈，也就是說這 $n_1+\dots+n_k$ 處穴位通過經脈兩兩連通。也就是說如果將穴位看成點，穴位之間的經脈看成邊，那麼需要構成連通圖。已知對於兩個分別處於 $i,j$ 維度的穴位，打通這兩個穴位有 $a_{i,j}$ 種方法。注意處於同一個維度的穴位之間也可以打通，但一個穴位不能和自己打通。

請你自行計算一下，有多少種方法可以給你打通經脈。由於方案數很多，你只需要算出同餘 $998244353$ 的結果。

輸入格式

第一行包含一個正整數 $k$，表示你所處的空間維度。

接下來一行輸入 $k$ 個正整數，第 $j$ 個表示 $n_j$，即你在第 $j$ 個維度的穴位數量。

接下來輸入 $k$ 行，每行 $k$ 個整數，其中第 $i$ 行第 $j$ 個數表示 $a_{i,j}$，保證 $a_{i,j}=a_{j,i}$。

輸出格式

輸出一行一個整數，表示打通經脈的方案數，同餘 $998244353$ 的結果。

範例

輸入 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)$。

對於 $100\%$ 的資料，保證 $N\le 2.5\times 10^5, 0\le a_{i,j} < 998244353$。