#P18552. Exchanging Kubic 2

Exchanging Kubic 2

Exchanging Kubic 2

小青鱼正在与 Kubic 教授进行一项社会实验。实验中有 n 个人,初始位置分别为 a_1,a_2,…,a_n。你必须恰好进行 n 次操作,每个人只能被选择一次。

每次操作选择一个人,其他所有人同时向这个被选中的人移动一步。具体地,选择第 i 个人时,对每个 j≠i,以本次操作开始时的位置进行比较:

  • 若 a_i>a_j,则 a_j←a_j+1;
  • 若 a_i<a_j,则 a_j←a_j−1;
  • 若 a_i=a_j,则 a_j 保持不变。

被选中的人本次不移动。已经被选择过的人以后仍会按上述规则移动,只是不能再次成为被选中的人。

定义数组 a=(a_1,…,a_n) 的价值:安排全部 n 次操作的顺序,使操作结束后距离最远的两个人之间的距离尽可能小;这个最小距离就是数组的价值。n=1 时该距离为0。

现在给定 n 个集合 S_1,S_2,…,S_n。数组 a 合法当且仅当同时满足:

  1. 对所有1≤i<n,有 a_i≤a_{i+1};
  2. 对所有1≤i≤n,有 a_i∈S_i。

请计算所有合法数组的价值之和,答案对998244353取模。不同合法数组各计算一次;操作顺序只用于确定一个数组的最小价值,不作为求和中的不同方案。若没有合法数组,和为0。

输入格式

第一行一个整数 n(1≤n≤400)。

接下来 n 行依次描述 S_i。每行先给出整数 |S_i|(0≤|S_i|≤801),随后给出 |S_i| 个互不相同的整数,均在[0,800]内,表示集合的元素。

集合元素不保证按大小排序。集合可以为空。输入仅包含这一组数据。

输出格式

输出一行一个整数,表示所有合法数组价值之和对998244353取模的结果。

原样例1

5
3 1 2 3
1 2
0
4 0 2 3 4
2 2 3
0

原样例2

5
4 1 2 3 7
4 5 7 8 9
4 2 3 6 9
5 0 1 4 7 9
8 0 1 2 3 6 7 8 9
16