配点 : 300 点
問題文
N \times N 方格。 i = 1,2,\dots,N ,从左起: i 列从下方开始有 M_i 的 您可以创建一个包含 1 \times 1 个正方形的方块,每个方块都被涂上了颜色。这里, M_1,M_2,\dots,M_N 是单调非增的。从左边开始,第 i 列从下方数第 j 个方块被涂上了颜色 C_{i,j} 。
对于方格,考虑以下操作:
- 将方格顺时针瞬间旋转 90^\circ 次,然后令有颜色的方块按照重力同时下落。更正式地说,对于左起第 i 列从下方数第 j 个方块,如果在与该方块同一高度、该方块右侧有 c_{i,j} 个方块,则将该方块移动到左起第 j 列从下方数第 c_{i,j}+1 个方格。此移动将同时对所有方块进行。
要使网格恢复到最初的布局,至少需要多少次操作呢? 998244353 求除以后的余数。
网格布局一致性的定义
对网格布局, N \times N 行列 A 进行对应。 A_{i,j} \, (i,j=1,2,\dots,N) 通过以下方式来确定。- 从网格的左边开始 i 列从下方数第 j 如果在第 x 个格子中存在方块,则为其颜色;如果不存在,则为…… 0
制約
- 2 \leq N \leq 10^5
- 1 \leq \displaystyle \sum_{i=1}^N M_i \leq 10^5
- N \geq M_1 \geq M_2 \geq \dots \geq M_N \geq 0
- 1 \leq C_{i,j} \leq 10^5
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
M_1 C_{1,1} C_{1,2} \dots C_{1,M_1}
M_2 C_{2,1} C_{2,2} \dots C_{2,M_2}
\vdots
M_N C_{N,1} C_{N,2} \dots C_{N,M_N}
出力
答案 请打印除以 998244353 除以的余数。
入力例 1
2 2 1 2 1 3
出力例 1
3
通过操作,颜色的布局将如下变化。在这个例子中, 3 几次操作后可以恢复到原来的状态。

入力例 2
2 2 1 1 1 1
出力例 2
1
入力例 3
3 3 1 2 3 1 4 0
出力例 3
6
入力例 4
5 5 1 2 3 4 5 4 6 7 7 9 3 10 7 12 2 13 14 0
出力例 4
22