#P17864. 众数

众数

F. 众数

给定 n×nn\times n 的矩阵 WW。考虑所有长度为 nn、元素取自 {1,2,…,n}\{1,2,\ldots,n\} 的序列 aa。

令 bib_i 表示前缀 a1,…,aia_1,\ldots,a_i 中,出现次数达到该前缀最高出现次数的不同数值的数量。例如前缀 (1,2,1,2,3)(1,2,1,2,3) 中,1,21,2 并列出现最多,因此对应的 bi=2b_i=2。

序列权值为 ∏i=1nwi,bi\prod_{i=1}^{n}w_{i,b_i}。求所有 nnn^n 个序列的权值之和,对 998244353998244353 取模。

输入格式

第一行一个整数 1≤n≤1001\le n\le100。随后 nn 行,每行 nn 个整数,表示矩阵的一行。0≤wi,j<9982443530\le w_{i,j}<998244353。本题只有一组数据。

输出格式

输出一个整数,即权值和模 998244353998244353 的结果。

样例 1

输入:

1
7

输出:

7

样例 2

输入:

2
1 2
3 4

输出:

14

样例 3

输入:

3
1 1 1
3 1 1
0 0 1

输出:

6