给定三个整数 $$$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 31 1 2414 3
输出复制
2
输入复制
3 5 21 152
输出复制
13
输入复制
200000 12345678 73 2 5 1 3 4 542 13 3737 131 2 3 4 533 1 41 5 9 21 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$$$ 包含它作为子序列。