Dany jest bardzo duży graf, posiadający łącznie $n_1+\dots+n_k$ wierzchołków, które nazywamy odpowiednio częściami $1, 2, \dots, k$. Dla każdej pary części $i$ oraz $j$, albo wszystkie możliwe krawędzie między nimi istnieją, albo żadna z nich nie istnieje.
Lan chce wiedzieć, ile drzew rozpinających posiada ten graf, więc pyta o to Aige. Aige jednak, zgodnie z oczekiwaniami, zignorowała pytanie, więc Lan musi zapytać Ciebie. Wystarczy, że podasz wynik modulo $998244353$.
Wejście
W pierwszej linii znajduje się liczba całkowita dodatnia $k$, oznaczająca liczbę części grafu.
W kolejnej linii znajduje się $k$ liczb całkowitych dodatnich $n_1, \dots, n_k$, oznaczających liczbę wierzchołków w każdej z części.
W kolejnych $k$ liniach znajduje się po $k$ liczb całkowitych, równych $0$ lub $1$, gdzie $a_{i,j} = 1$ oznacza, że wszystkie krawędzie między częścią $i$ a częścią $j$ istnieją, w przeciwnym razie żadna z nich nie istnieje.
Wyjście
Wypisz jedną liczbę całkowitą oznaczającą liczbę drzew rozpinających modulo $998244353$.
Przykład
Przykład 1
Wejście:
2 2 2 1 1 1 0
Wyjście:
8
Przykład 2
Wejście:
4 12 34 56 78 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
Wyjście:
353527476
Podzadania
Dla $100\%$ danych wejściowych zachodzą warunki: $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}$.
| Test | Ograniczenia specjalne |
|---|---|
| $1$ | Graf jest grafem pełnym |
| $2$ | Graf jest pełnym grafem dwudzielnym |
| $3$ | $k=2$ |
| $4$ | $k=3$ |
| $5$ | $a_{i,j}=[i\neq j], n_i=n_j$ |
| $6,7$ | $n_i = 1$ |
| $8$ | $k\le 9$ |
| $9,10$ | Brak |