Чтобы хорошо владеть «молниеносным хлыстом» (松活弹抖闪电鞭), нужно сначала освоить трехмерную силу «хуньюань» (混元劲).

Мастер Ма — мастер тайцзи в многомерном пространстве. Основываясь на своем опыте обучения кулачному бою в $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

Выходные данные

12

Примечание

Всего имеется $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

Выходные данные

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$.