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