Counting Generalized Stirling Permutations

For a given positive integer \(\alpha\), an (n,\alpha)-permutation is defined as a sequence \(a\) of length \(\alpha n\) satisfying the following properties:

• For every \(k=1,2,\dots,n\), the number \(k\) appears exactly \(\alpha\) times in \(a\).
• If \(i<j\) and \(a_i=a_j\), then for every index \(k\) with \(i<k<j\) it holds that \(a_k\ge a_i\). In other words, between any two occurrences of the same number, all elements are at least that number.

Such sequences are also known as generalized Stirling permutations. Now, you are given a generalized Stirling permutation \(P\) of order \(n_0\) (thus, \(P\) is a \((n_0,\alpha)\)-permutation), and two integers \(n\) and \(m\). Your task is to count the number of \((n,\alpha)\)-permutations that satisfy both of the following conditions:

• The sequence contains \(P\) as a subsequence (not necessarily contiguous).
• The sequence has exactly \(m\) indices \(i\) such that \(a_i>a_{i+1}\) (i.e. exactly \(m\) descents).

Since the answer can be very large, output it modulo \(998244353\).

Note: When writing formulas, use LaTeX format. For example, write \(\alpha\) for the parameter alpha.

inputFormat

The input is given as follows:

 n m \(\alpha\)
 n0
 P[1] P[2] ... P[\(n_0 \times \alpha\)]

Here:

• \(n\) and \(\alpha\) define the \((n,\alpha)\)-permutation.
• \(m\) is the required number of descents (i.e. positions \(i\) with \(a_i>a_{i+1}\)).
• \(n_0\) is the order of the given permutation \(P\), and \(P\) is a \((n_0,\alpha)\)-permutation (thus it has exactly \(\alpha n_0\) numbers).

outputFormat

Output a single integer: the number of \((n,\alpha)\)-permutations which contain \(P\) as a subsequence and have exactly \(m\) descents, taken modulo \(998244353\).

sample

2 0 2
1
1 1

1