Oblivionis в последний раз взглянула на свой дом перед отъездом, твердо решив оставить прошлое позади. Она хотела, чтобы магия времени вновь превратила ее хаотичное сердцебиение в здоровый, гармоничный ритм. Но прежде чем она смогла по-настоящему забыть обо всем, в ее сознании возник вопрос: что, если бы события прошлого разворачивались в ином порядке? Был бы результат другим, и изменилось бы ее понимание этого?

Дана матрица $n \times n$ $A$ над полем $\mathbb{F}_{998244353}$. Рассмотрим, сколько матриц $B$ коммутируют с $A$, то есть сколько матриц удовлетворяют условию $AB = BA$. Можно доказать, что существует такое целое положительное число $k$, что количество таких матриц равно $998244353^k$. Определите значение $k$.

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

Первая строка входных данных содержит единственное целое число $n$ ($1 \le n \le 500$).

Следующие $n$ строк описывают матрицу $A$. $i$-я из этих строк содержит $n$ целых чисел $A_{ij}$ ($0 \le A_{ij} < 998244353$), задающих матрицу $A$.

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

Выведите одну строку с единственным целым числом — ответом $k$.

Примеры

Пример 1

3
1 2 3
4 5 6
7 8 9

3

Пример 2

3
1 1 0
0 1 0
0 0 1

5