CF2169F.Subsequence Problem

Given three integers $n, m, k$, as well as $k$ arrays of integers of lengths $l_1, l_2, \dots, l_k$ respectively. We denote the element at position $j$ in array number $i$ as $a_{i,j}$. In each array, all elements are distinct (but may repeat in different arrays).

We call an array $b$ of length $k$ beautiful if for each $i$ from $1$ to $k$, the element $b_i$ is equal to one of the elements of the array $a_i$.

We call an array $c$ perfect if every beautiful array $b$ can be obtained from array $c$ by deleting several (possibly zero) elements without changing their order. In other words, array $c$ is perfect if every beautiful array $b$ is a subsequence of it.

Your task is to count the number of perfect arrays $c$ of length $n$ containing only integers from $1$ to $m$.

给定三个整数 $n, m, k$，以及 $k$ 个整数数组，其长度分别为 $l_1, l_2, \dots, l_k$。我们用 $a_{i,j}$ 表示第 $i$ 个数组中位置 $j$ 处的元素。在每个数组中，所有元素互不相同（但不同数组之间可以有重复元素）。

我们称一个长度为 $k$ 的数组 $b$ 是优美的（beautiful），如果对每个 $i$（$1 \le i \le k$），元素 $b_i$ 都等于数组 $a_i$ 中的某个元素。

我们称一个数组 $c$ 是完美的（perfect），如果每一个优美的数组 $b$ 都可以通过从 $c$ 中删除若干（可能为零）个元素（不改变剩余元素的相对顺序）而得到。换言之，数组 $c$ 是完美的，当且仅当每一个优美的数组 $b$ 都是 $c$ 的一个子序列（subsequence）。

你的任务是：计算长度为 $n$、且仅包含 $1$ 到 $m$ 之间整数的完美数组 $c$ 的个数。

The first line contains three integers $n, m, k$ ($2 \le n \le 2 \cdot 10^5$; $5 \le m \le 10^8$; $2 \le k \le n$).

The second line contains $k$ integers $l_1, l_2, \dots, l_k$ ($1 \le l_i \le 5$).

The following $k$ lines contain the $i$-th line with $l_i$ distinct integers $a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$ ($1 \le a_{i,j} \le m$).

Additional constraint on the input: the sum of $l_i$ does not exceed $n$.

第一行包含三个整数 $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$。

Print one integer — the number of perfect arrays of length $n$ such that they contain only integers from $1$ to $m$. Since the answer may be very large, output it modulo $998244353$.

输出一个整数——长度为 $n$ 且仅包含 $1$ 到 $m$ 之间整数的完美数组的个数。由于答案可能非常大，请对 $998244353$ 取模后输出。

In the first example, there are two beautiful arrays: $[4, 1, 4]$ and $[4, 1, 3]$. Only two arrays of length $4$ contain both of these arrays as subsequences: $[4, 1, 4, 3]$ and $[4, 1, 3, 4]$.

In the second example, there is only one beautiful array: $[5, 2]$. There are $13$ arrays of length $3$ with integers from $1$ to $5$ that contain it as a subsequence.

在第一个例子中，有两个优美的数组：$[4, 1, 4]$ 和 $[4, 1, 3]$。仅有两个长度为 $4$ 的数组同时以这两个数组作为子序列：$[4, 1, 4, 3]$ 和 $[4, 1, 3, 4]$。

在第二个例子中，仅有一个优美的数组：$[5, 2]$。共有 $13$ 个长度为 $3$、元素取自 $1$ 到 $5$ 的数组，使得该数组为其子序列。