Aby opanować technikę „songhuo dandou shandian bian”, należy najpierw opanować trójwymiarową energię „hunyuan jin”.

Mistrz Ma jest mistrzem sztuk walki Tai Chi w wysokich wymiarach. Na podstawie swoich doświadczeń w nauczaniu w przestrzeni $k$-wymiarowej zauważył, że jako istota $k$-wymiarowa posiadasz $n_1+\dots+n_k$ punktów akupunkturowych, z czego $n_j$ punktów pochodzi z $j$-tego wymiaru. Aby opanować $k$-wymiarową energię „hunyuan jin”, musisz najpierw odblokować swoje meridiany, co oznacza, że wszystkie $n_1+\dots+n_k$ punktów musi być połączonych parami za pomocą meridianów. Innymi słowy, jeśli potraktujemy punkty jako wierzchołki, a meridiany jako krawędzie, musimy utworzyć graf spójny. Wiadomo, że dla dwóch punktów znajdujących się odpowiednio w wymiarach $i$ oraz $j$, istnieje $a_{i,j}$ sposobów na połączenie tych dwóch punktów. Zauważ, że punkty w tym samym wymiarze również mogą być połączone, ale punkt nie może być połączony sam ze sobą.

Oblicz, na ile sposobów możesz odblokować meridiany. Ponieważ liczba sposobów może być bardzo duża, podaj wynik modulo $998244353$.

Wejście

Pierwsza linia zawiera liczbę całkowitą dodatnią $k$, oznaczającą wymiar przestrzeni, w której się znajdujesz.

W kolejnej linii znajduje się $k$ liczb całkowitych dodatnich, gdzie $j$-ta liczba oznacza $n_j$, czyli liczbę punktów w $j$-tym wymiarze.

Następnie podano $k$ linii, z których każda zawiera $k$ liczb całkowitych. Liczba w $i$-tym wierszu i $j$-tej kolumnie oznacza $a_{i,j}$. Gwarantuje się, że $a_{i,j}=a_{j,i}$.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą liczbę sposobów na odblokowanie meridianów, modulo $998244353$.

Przykład

Wejście 1

2
2 1
1 2
2 1

Wyjście 1

12

Uwagi 1

Łącznie mamy $2+1=3$ węzły. Pomiędzy $(1,2)$ istnieje $1$ sposób połączenia, a pomiędzy $(1,3)$ oraz $(2,3)$ istnieją po $2$ sposoby połączenia.

Jeśli połączymy $(1,2)$, to pozostałe połączenia można wykonać na $(2+1)^2-1=8$ sposobów.

Jeśli nie połączymy $(1,2)$, to $(1,3)$ oraz $(2,3)$ muszą zostać połączone niezależnie, co daje $2\times 2 = 4$ sposoby.

Łącznie istnieje $8+4=12$ sposobów.

Wejście 2

2
7 4
1 998244352
998244352 0

Wyjście 2

188336

Ograniczenia

Niech $N=(n_1+1)\times \dots \times(n_k+1)$.

Dla $100\%$ danych wejściowych gwarantuje się, że $N\le 2.5\times 10^5$ oraz $0\le a_{i,j} < 998244353$.