Дан большой граф, состоящий в общей сложности из $n_1+\dots+n_k$ вершин, которые мы будем называть частями $1, 2, \dots, k$. Для любых двух частей $i$ и $j$ либо все пары вершин между ними соединены ребрами, либо ни одна пара не соединена.

Лань хочет узнать количество остовных деревьев в этом графе и обращается с этим вопросом к Айгэ. Однако Айгэ, как и ожидалось, проигнорировала её, поэтому она вынуждена спросить вас. Вам нужно вывести ответ по модулю $998244353$.

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

В первой строке вводится положительное целое число $k$, обозначающее количество частей графа.

В следующей строке вводятся $k$ положительных целых чисел $n_1, \dots, n_k$, обозначающих количество вершин в каждой части.

В следующих $k$ строках вводится по $k$ целых чисел ($0$ или $1$), где $a_{i,j} = 1$ означает, что все пары вершин между частью $i$ и частью $j$ соединены ребрами, в противном случае — не соединены.

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

Выведите одно целое число — количество остовных деревьев по модулю $998244353$.

Примеры

Пример 1

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

2
2 2
1 1
1 0

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

8

Пример 2

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

4
12 34 56 78
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

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

353527476

Подзадачи

Для $100\%$ данных гарантируется, что $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}$.