Occurrences
Contest: Educational Codeforces Round 114 (Rated for Div. 2)
Difficulty rating: 2700
Tags: combinatorics, dfs and similar, dp, dsu, fft, graphs

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$$$.

Input format:
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$$$.

Output format:
Print one integer — the number of different arrays $$$a$$$ you can build, taken modulo $$$998244353$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Example input:
2 4 3
2 1 2
1 3

Example output:
5

Example input:
2 4 3
2 1 2
3 3 2 1

Example output:
0

Editorial:
What does the condition "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$$$" mean? First, if $$$A_i$$$ contains two (or more) equal elements, then any occurrence of $$$A_i$$$ introduces at least two occurrences of that element; so any element in $$$A_i$$$ is forbidden (it should not appear in the resulting array). Now let's consider an array $$$A_i$$$ such that every its element is unique. Every element of $$$A_i$$$ should be a part of an occurrence of $$$A_i$$$ in the array $$$a$$$. Let's rephrase this condition as follows: for each occurrence of $$$A_{i,j}$$$ in $$$a$$$, the next element in $$$a$$$ is $$$A_{i,j+1}$$$, and vice versa: for each occurrence of $$$A_{i,j+1}$$$ in $$$a$$$, the previous element in $$$a$$$ is $$$A_{i,j}$$$.
Let's build a directed graph on $$$k$$$ vertices, where an arc from vertex $$$x$$$ to vertex $$$y$$$ means that each occurrence of $$$x$$$ should be followed by $$$y$$$, and each occurrence of $$$y$$$ should be preceded by $$$x$$$ (i. e. $$$x$$$ is followed by $$$y$$$ in some array $$$A_i$$$). Let's consider the weakly connected components in this graph. If we have at least one occurrence of some element from a component in $$$a$$$, it means that all other elements from this component occur in $$$a$$$ as well. Some integers from $$$1$$$ and $$$k$$$ are "bad" in a sense that we cannot uniquely determine which element should follow/precede them (in terms of graph theory, it means that the in-degree or out-degree of a vertex is at least $$$2$$$). Since by picking one element from a component, we will have to use all elements from a component, it means that if a component contains at least one "bad" element, the whole component will be "bad" — we cannot use any element from it.
If a component is a cycle, no vertex has in-degree or out-degree greater than $$$1$$$, but the component is still "bad" since, if we include at least one element from $$$a$$$, we cannot finish the cycle — the array $$$a$$$ is not infinite, but the cycle is.
Okay, the only "good" components are chains. When we use an element from a chain in $$$a$$$, all elements from this chain will be used in exactly the same order that they were in the chain; so, $$$a$$$ should consist of some chains linked together (chains may repeat, and some chains may be absent from $$$a$$$). We can write a solution with dynamic programming: let $$$dp_i$$$ be the number of ways to construct an array of length $$$i$$$ using these chains. The transitions are as follows: $$$dp_i = \sum\limits_{j=1}^{c} dp_{i - len_j}$$$, where $$$c$$$ is the number of chains, and $$$len_j$$$ is the length of the $$$j$$$-th chain.
The number of chains is up to $$$k$$$, and the number of states in dynamic programming is $$$m + 1$$$, so the solution works in $$$O(mk)$$$, which is too slow. We can improve it with the following two facts:
• all chains of the same length are indistinguishable;
• there are $$$O(\sqrt{k})$$$ different lengths of chains.
So, instead of iterating on the chains themselves in dynamic programming, we will iterate on the lengths of the chains (considering only lengths having at least one chain), and process all chains of the same length as one by introducing a multiplier in our dynamic programming: $$$dp_i = \sum \limits_{j=1}^{k} dp_{i - j} \cdot cnt_j$$$, where $$$cnt_j$$$ is the number of chains of length $$$j$$$. That way, our dynamic programming will work in $$$O(m \sqrt{k})$$$ if we skip the values of $$$j$$$ with $$$cnt_j = 0$$$.