Oblivionis 在离开前最后看了一眼家，毅然决定将过去抛在脑后。她希望时间的魔法能将她此刻混乱的心跳重新塑造成健康、和谐的节奏。但在她真正忘记一切之前，一个问题萦绕在她的脑海中：如果过去的事件以不同的顺序发生会怎样？结果会不同吗？她对结果的理解也会改变吗？

给定一个定义在 $\mathbb{F}_{998244353}$ 上的 $n \times n$ 矩阵 $A$，考虑有多少个矩阵 $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

样例输出 1

3

样例输入 2

3
1 1 0
0 1 0
0 0 1

样例输出 2

5