У Little Cyan Fish есть матрица $W$ размера $n \times n$.

Для целочисленной последовательности $a_1, a_2, \ldots, a_n$, в которой $1 \le a_i \le n$, обозначим через $b_i$ количество различных целых чисел, которые встречаются наибольшее число раз в префиксе $a_1, a_2, \ldots, a_i$. Например, в префиксе $1, 2, 1, 2, 3$ числа $1$ и $2$ встречаются по два раза, поэтому $b_5 = 2$.

Little Cyan Fish определяет вес последовательности как

$$\prod_{i=1}^n w_{i,b_i}.$$

Найдите сумму весов всех таких последовательностей. Поскольку ответ может быть очень большим, выведите его по модулю $998\,244\,353$.

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

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 100$) — длину последовательностей и размер матрицы.

Следующие $n$ строк описывают матрицу $W$. $i$-я из этих строк содержит $n$ целых чисел $w_{i,1}, w_{i,2}, \ldots, w_{i,n}$ ($0 \le w_{i,j} < 998\,244\,353$).

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

Выведите одну строку, содержащую одно целое число — сумму весов всех таких последовательностей по модулю $998\,244\,353$.

Примеры

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

1
7

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

7

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

2
1 2
3 4

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

14

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

3
1 1 1
3 1 1
0 0 1

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

6

Примечание

В первом тестовом примере единственная последовательность — это $(1)$, и её вес равен $7$.

Во втором тестовом примере последовательности $(1, 1)$ и $(2, 2)$ имеют вес $3$ каждая, а последовательности $(1, 2)$ и $(2, 1)$ имеют вес $4$ каждая. Сумма равна $3 + 3 + 4 + 4 = 14$.

В третьем тестовом примере последовательность имеет ненулевой вес тогда и только тогда, когда все три значения различны. Таких последовательностей шесть, и вес каждой из них равен $1$.