← 返回题目列表

Codeforces · 1279/D

D. 圣诞老人的机器人

中文机器翻译题面 查看原题

圣诞老人今年全年收到了来自 $$$n$$$ 不同孩子的来信。当然,每个孩子都想从圣诞老人那里得到一些礼物:特别是,第 $$$i$$$ 个孩子要求圣诞老人给他们一个 $$$k_i$$$ 不同的物品作为礼物。有些项目可能会被多个孩子询问。

圣诞老人真的很忙,所以他希望新年机器人为所有孩子选择礼物。不幸的是,机器人选择礼物的算法有问题。为了给某个孩子选择一份礼物,机器人会执行以下操作:

- 在所有 $$$n$$$ 孩子中同等概率地选择一个孩子 $$$x$$$;
- 在孩子 $$$x$$$ 想要的所有 $$$k_x$$$ 项目中等概率地选择某个项目 $$$y$$$;
- 选择一个孩子$$$z$$$,他将在所有$$$n$$$孩子中平均收到礼物(此选择与选择$$$x$$$和$$$y$$$无关)​​;由此产生的三元组 $$$(x, y, z)$$$ 称为机器人的决策。

如果孩子 $$$z$$$ 将 $$$y$$$ 列为他们想要收到的物品,则该决定有效。否则,Bot的选择无效。

圣诞老人知道这个错误,但他无法估计这个错误是否真的很严重。为此,他想知道根据上述算法生成的一个决策有效的概率。你能帮助他吗?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 给圣诞老人写信的孩子数量。

然后是 $$$n$$$ 行,其中第 $$$i$$$ 包含第 $$$i$$$ 个孩子想要的物品列表,格式如下: $$$k_i$$$ $$$a_{i, 1}$$$ $$$a_{i, 2}$$$ ... $$$a_{i, k_i}$$$ ($$$1 \le k_i, a_{i, j} \le 10^6$$$),其中 $$$k_i$$$ 是第 $$$i$$$ 个孩子想要的物品数量,$$$a_{i, j}$$$ 是物品本身。同一列表中的任何项目只能包含一次。

保证 $$$\sum \limits_{i = 1}^{n} k_i \le 10^6$$$。

输出

打印机器人产生有效决策的概率,如下所示:

将此概率表示为不可约分数 $$$\frac{x}{y}$$$。您必须打印 $$$x \cdot y^{-1} \mod 998244353$$$,其中 $$$y^{-1}$$$ 是 $$$y$$$ 模 $$$998244353$$$ 的逆元素(这样的整数 $$$y \cdot y^{-1}$$$ 具有余数 $$$1$$$ 模$$$998244353$$$)。

示例

输入 #1

2
2 2 1
1 1

输出 #1

124780545

输入 #2

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

输出 #2

798595483