Oblivionisは出発前に故郷を最後にもう一度振り返り、過去を断ち切る決意をした。彼女は、時の魔法が今の混沌とした鼓動を再び健全で調和のとれたリズムへと作り変えてくれることを願った。しかし、すべてを完全に忘れてしまう前に、一つの疑問が彼女の心に残った。もし過去の出来事が別の順序で起こっていたらどうなっていただろうか？結果は異なっていたのだろうか、そしてそれに対する彼女の理解も変わっていたのだろうか？

$\mathbb{F}_{998244353}$ 上の $n \times n$ 行列 $A$ が与えられる。$A$ と可換な行列 $B$、すなわち $AB = BA$ を満たす行列 $B$ がいくつ存在するかを考えよ。そのような行列の個数は $998244353^k$ となるような正の整数 $k$ が存在することが証明できる。この $k$ の値を求めよ。

入力

入力の最初の行には、整数 $n$ ($1 \le n \le 500$) が含まれる。

続く $n$ 行は行列 $A$ を表す。これらの行のうち $i$ 番目の行には、$n$ 個の整数 $A_{ij}$ ($0 \le A_{ij} < 998244353$) が含まれており、行列 $A$ の成分を表す。

出力

答えである整数 $k$ を1行で出力せよ。

入出力例

入力 1

3
1 2 3
4 5 6
7 8 9

出力 1

3

入力 2

3
1 1 0
0 1 0
0 0 1

出力 2

5