← 返回题目列表

Codeforces · 1574/F

F. 发生次数

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

数组 $$$a$$$ 从索引 $$$l$$$ 到索引 $$$r$$$ 的子数组是数组 $$$[a_l, a_{l+1}, \dots, a_{r}]$$$。数组 $$$b$$$ 在数组 $$$a$$$ 中出现的次数是 $$$a$$$ 中等于 $$$b$$$ 的子数组的数量。

给你 $$$n$$$ 数组 $$$A_1, A_2, \dots, A_n$$$;这些数组的元素是从 $$$1$$$ 到 $$$k$$$ 的整数。您必须构建一个由 $$$1$$$ 到 $$$k$$$ 之间的 $$$m$$$ 整数组成的数组 $$$a$$$,使得对于每个给定的子数组 $$$A_i$$$,$$$A_i$$$ 在数组 $$$a$$$ 中出现的次数不小于 $$$A_i$$$ 中每个非空子数组的出现次数$$$a$$$。请注意,如果 $$$A_i$$$ 没有出现在 $$$a$$$ 中,并且 $$$A_i$$$ 的子数组没有出现在 $$$a$$$ 中,则 $$$A_i$$$ 仍然满足此条件。

你的任务是计算你可以构建的不同数组 $$$a$$$ 的数量,并将其模 $$$998244353$$$ 打印出来。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m, k \le 3 \cdot 10^5$$$) — 给定数组的数量、数组 $$$a$$$ 的所需长度以及数组中值的上限。

然后是 $$$n$$$ 行。第 $$$i$$$ 行表示数组 $$$A_i$$$。第 $$$i$$$ 行中的第一个整数是 $$$c_i$$$ ($$$1 \le c_i \le m$$$) — $$$A_i$$$ 中的元素数量;然后,$$$c_i$$$ 是从 $$$1$$$ 到 $$$k$$$ 的整数 — 数组 $$$A_i$$$ 的元素。

输入的附加约束:$$$\sum\limits_{i=1}^n c_i \le 3 \cdot 10^5$$$;我。即,给定数组中的元素总数不超过 $$$3 \cdot 10^5$$$。

输出

打印一个整数 — 您可以构建的不同数组 $$$a$$$ 的数量,以 $$$998244353$$$ 为模。

示例

输入 #1

2 4 3
2 1 2
1 3

输出 #1

5

输入 #2

2 4 3
2 1 2
3 3 2 1

输出 #2

0

输入 #3

1 42 1337
2 13 31

输出 #3

721234447