F. 众数
给定 n×n 的矩阵 W。考虑所有长度为 n、元素取自 {1,2,…,n} 的序列 a。
令 bi 表示前缀 a1,…,ai 中,出现次数达到该前缀最高出现次数的不同数值的数量。例如前缀 (1,2,1,2,3) 中,1,2 并列出现最多,因此对应的 bi=2。
序列权值为 ∏i=1nwi,bi。求所有 nn 个序列的权值之和,对 998244353 取模。
输入格式
第一行一个整数 1≤n≤100。随后 n 行,每行 n 个整数,表示矩阵的一行。0≤wi,j<998244353。本题只有一组数据。
输出格式
输出一个整数,即权值和模 998244353 的结果。
样例 1
输入:
1
7
输出:
7
样例 2
输入:
2
1 2
3 4
输出:
14
样例 3
输入:
3
1 1 1
3 1 1
0 0 1
输出:
6