Subsequence Problem

Let $A_i$ be the set from row $i$. The scary phrase is every beautiful array. Do not build a state for all products; that road explodes instantly.

The Split Lemma Look at a candidate word $c$ and the first position $t$ where the prefix contains every value of $A_1$. If such a position does not exist, $c$ obviously is not perfect.

Let $z=c_t$. Because $t$ is the first completion time, $z\in A_1$ and $z$ did not appear earlier. Suppose $c$ is perfect. Take any valid tail $d_2,\dots,d_k$ with $d_i\in A_i$. The sequence $(z,d_2,\dots,d_k)$ must be a subsequence of $c$. Its first element cannot be matched before $t$, so the whole tail must appear after $t$. Therefore the suffix after $t$ is perfect for $A_2,\dots,A_k$.

The reverse direction is easy: if a prefix up to $t$ contains all of $A_1$ and the suffix after $t$ is perfect for the rest, choose $b_1$ inside the prefix and match the rest in the suffix.

So every perfect word has a unique recursive decomposition: finish $A_1$ for the first time, then finish $A_2$ for the first time in the remaining suffix, and so on. This is the whole trick. The actual values are bait; only the lengths matter.

Counting One Segment Consider one array of length $L$. In its segment, the $L$ required values make their first appearances in some order. There are $L!$ choices for that order.

Before the first new required value appears, none of the $L$ required values may appear, so each filler character has $m-L$ choices. After one required value has appeared, filler may use irrelevant values and that seen value, but not the remaining $L-1$ unseen required values, so there are $m-(L-1)$ choices. In general, while $q$ required values are still unseen, filler characters have $m-q$ choices. Then the next character is the first appearance of one of those unseen values.

After all $k$ arrays are finished, the remaining suffix has no restrictions, so it contributes one more filler zone with $m$ choices per character.

The canonical decomposition prevents double counting. For a fixed word, the completion positions and first-appearance orders are forced.

Generating Function Let

$S=\sum_{i=1}^k l_i,\qquad D=n-S.$

The $S$ required first-appearance characters are already fixed by the segment orders. We only need to distribute $D$ extra filler characters among the filler zones.

For $q\ge 1$, a segment with length at least $q$ has exactly one filler zone where $q$ required values are still unseen. Define

$s_0=1,\qquad s_q=|\{i:l_i\ge q\}|\quad(1\le q\le 5).$

A filler zone with $m-q$ choices per character contributes

$1+(m-q)x+(m-q)^2x^2+\cdots=\frac{1}{1-(m-q)x}.$

Therefore the answer is

$\left(\prod_{i=1}^k l_i!\right)[x^D]\prod_{q=0}^{5}(1-(m-q)x)^{-s_q}.$

Notice why overlaps between different arrays do not change anything. When we are inside segment $i$, the only question is whether a value belongs to the unseen part of $A_i$. Future arrays are not active yet. Same integer, different segment, fresh obligation. Annoying, yes, but also clean as hell.

Computing The Coefficient Use the negative binomial expansion:

$(1-\alpha x)^{-s}=\sum_{t\ge 0}\binom{t+s-1}{t}\alpha^t x^t.$

Build the six polynomials up to degree $D$, multiply them modulo $998244353$, and take coefficient $D$. Since $D\le 2\cdot 10^5$ and there are only six factors, NTT is the right hammer here.

Factorials up to $n$ are enough for all binomial coefficients. Finally multiply by $\prod l_i!$.