#P18562. Homeward Glance

Homeward Glance

Homeward Glance

Oblivionis 在离家之前最后回望了一眼,决心把过去抛在身后。她希望时间的魔力能让自己如今混乱的心跳重新变得健康而和谐。但是,在真正忘记一切之前,一个问题仍萦绕在她心中:如果过去的事件以不同的顺序发生,结果会不会不同?她对它的理解是否也会改变?

给定有限域 F998244353\mathbb F_{998244353} 上的一个 n×nn\times n 矩阵 AA,考虑有多少个矩阵 BB 与 AA 交换,即满足

AB=BA.AB=BA.

可以证明,存在正整数 kk,使这样的矩阵 BB 的数量为 998244353k998244353^k。请确定 kk 的值。

域中的元素用 0,1,…,9982443520,1,\ldots,998244352 表示,矩阵运算在该有限域上进行。

输入格式

第一行一个整数 nn(1≤n≤5001\le n\le500)。

接下来 nn 行描述矩阵 AA。第 ii 行包含 nn 个整数 AijA_{ij}(0≤Aij<9982443530\le A_{ij}<998244353)。

输出格式

输出一行一个整数,表示答案 kk。注意输出的是指数,而不是矩阵数量。

原样例 1

3
1 2 3
4 5 6
7 8 9
3

原样例 2

3
1 1 0
0 1 0
0 0 1
5