← 返回题目列表

Codeforces · 2169/F

F. 后续问题

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

给定三个整数 $$$n、m、k$$$,以及长度分别为 $$$l_1、l_2、\dots、l_k$$$ 的整数数组 $$$k$$$。我们将数组编号 $$$i$$$ 中位置 $$$j$$$ 的元素表示为 $$$a_{i,j}$$$。在每个数组中,所有元素都是不同的(但可能在不同的数组中重复)。

如果对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$,元素 $$$b_i$$$ 等于数组 $$$a_i$$$ 的元素之一,我们称长度为 $$$k$$$ 的数组 $$$b$$$ 漂亮。

如果每个漂亮的数组 $$$b$$$ 都可以通过删除几个(可能是零)元素而不改变其顺序而从数组 $$$c$$$ 中获得,那么我们称数组 $$$c$$$ 是完美的。换句话说,如果每个漂亮的数组 $$$b$$$ 都是它的子序列,那么数组 $$$c$$$ 就是完美的。

你的任务是计算长度为 $$$n$$$ 且仅包含从 $$$1$$$ 到 $$$m$$$ 的整数的完美数组 $$$c$$$ 的数量。

输入

第一行包含三个整数 $$$n、m、k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$5 \le m \le 10^8$$$; $$$2 \le k \le n$$$)。

第二行包含 $$$k$$$ 整数 $$$l_1, l_2, \dots, l_k$$$ ($$$1 \le l_i \le 5$$$)。

以下 $$$k$$$ 行包含第 $$$i$$$ 行,其中包含 $$$l_i$$$ 不同整数 $$$a_{i,1}、a_{i,2}、\dots、a_{i,l_i}$$$ ($$$1 \le a_{i,j} \le m$$$)。

输入的附加约束:$$$l_i$$$ 的总和不超过$$$n$$$。

输出

打印一个整数 — 长度为 $$$n$$$ 且仅包含从 $$$1$$$ 到 $$$m$$$ 的整数的完美数组的数量。由于答案可能非常大,因此输出它对 $$$998244353$$$ 取模。

示例

输入
复制

4 5 3
1 1 2
4
1
4 3

输出
复制

2

输入
复制

3 5 2
1 1
5
2

输出
复制

13

输入
复制

200000 12345678 7
3 2 5 1 3 4 5
42 13 37
37 13
1 2 3 4 5
3
3 1 4
1 5 9 2
1 2 3 4 5

输出
复制

152094503

注意

在第一个示例中,有两个漂亮的数组:$$$[4, 1, 4]$$$ 和 $$$[4, 1, 3]$$$。只有两个长度为 $$$4$$$ 的数组包含这两个数组作为子序列:$$$[4, 1, 4, 3]$$$ 和 $$$[4, 1, 3, 4]$$$。

在第二个示例中,只有一个漂亮的数组:$$$[5, 2]$$$。有 $$$13$$$ 长度为 $$$3$$$ 的数组,其整数从 $$$1$$$ 到 $$$5$$$ 包含它作为子序列。