Oblivionis rzuciła ostatnie spojrzenie na dom przed wyjazdem, zdecydowanie postanawiając zostawić przeszłość za sobą. Pragnęła, aby magia czasu mogła ponownie ukształtować jej chaotyczne bicie serca w zdrowy, harmonijny rytm. Jednak zanim mogła naprawdę o wszystkim zapomnieć, w jej umyśle pojawiło się pytanie: co by było, gdyby wydarzenia z przeszłości potoczyły się w innej kolejności? Czy wynik byłby inny i czy jej zrozumienie tego również by się zmieniło?

Mając daną macierz $n \times n$ $A$ nad ciałem $\mathbb{F}_{998244353}$, rozważ, ile macierzy $B$ jest przemiennych z $A$, tzn. ile macierzy spełnia równanie $AB = BA$. Można udowodnić, że istnieje dodatnia liczba całkowita $k$ taka, że liczba takich macierzy wynosi $998244353^k$. Wyznacz wartość $k$.

Wejście

W pierwszej linii wejścia znajduje się pojedyncza liczba całkowita $n$ ($1 \le n \le 500$).

Kolejne $n$ linii opisuje macierz $A$. $i$-ta z tych linii zawiera $n$ liczb całkowitych $A_{ij}$ ($0 \le A_{ij} < 998244353$), określających macierz $A$.

Wyjście

Wypisz w jednej linii pojedynczą liczbę całkowitą, oznaczającą wynik $k$.

Przykład

Wejście 1

3
1 2 3
4 5 6
7 8 9

Wyjście 1

3

Wejście 2

3
1 1 0
0 1 0
0 0 1

Wyjście 2

5