Occurrences

题意翻译

定义 $a$ 的子序列是 $[a_l,a_{l+1},\cdots,a_r]$ 的连续子段构成的序列，定义 $a$ 序列在 $b$ 序列中出现的次数为 $b$ 序列中与 $a$ 相同的子序列个数。 有 $n$ 个值域在 $[1,k]$ 的数列 $A_1,A_2,\cdots,A_n$，要求构造一个长为 $m$ 的值域在 $[1,k]$ 的序列 $a$，满足对于所有数列 $A_i$，$A_i$ 在序列 $a$ 中的出现次数大于等于其任意一个非空子序列在 $a$ 中的出现次数。 求不同的 $a$ 的数量，答案 $\bmod 998244353$。 **数据范围**：$1\le n,m,k\le 3\times 10^5,\sum c_i\le 3\times 10^5$。

题目描述

A subarray of array $ a $ from index $ l $ to the index $ r $ is the array $ [a_l, a_{l+1}, \dots, a_{r}] $ . The number of occurrences of the array $ b $ in the array $ a $ is the number of subarrays of $ a $ such that they are equal to $ b $ . You are given $ n $ arrays $ A_1, A_2, \dots, A_n $ ; the elements of these arrays are integers from $ 1 $ to $ k $ . You have to build an array $ a $ consisting of $ m $ integers from $ 1 $ to $ k $ in such a way that, for every given subarray $ A_i $ , the number of occurrences of $ A_i $ in the array $ a $ is not less than the number of occurrences of each non-empty subarray of $ A_i $ in $ a $ . Note that if $ A_i $ doesn't occur in $ a $ , and no subarray of $ A_i $ occurs in $ a $ , this condition is still met for $ A_i $ . Your task is to calculate the number of different arrays $ a $ you can build, and print it modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 1 \le n, m, k \le 3 \cdot 10^5 $ ) — the number of the given arrays, the desired length of the array $ a $ , and the upper bound on the values in the arrays. Then $ n $ lines follow. The $ i $ -th line represents the array $ A_i $ . The first integer in the $ i $ -th line is $ c_i $ ( $ 1 \le c_i \le m $ ) — the number of elements in $ A_i $ ; then, $ c_i $ integers from $ 1 $ to $ k $ follow — the elements of the array $ A_i $ . Additional constraint on the input: $ \sum\limits_{i=1}^n c_i \le 3 \cdot 10^5 $ ; i. e., the number of elements in the given arrays in total does not exceed $ 3 \cdot 10^5 $ .

输出格式

Print one integer — the number of different arrays $ a $ you can build, taken modulo $ 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