Background

You keep walking forward and meet an old man in a black robe. In front of the door there is a huge sand table, and the old man draws strange symbols on it with a branch in his hand.

The old man tells you that he has dreamed of one problem since he was young. Even now that he is old and frail, it seems he has only uncovered a small part of the answer.

“Maybe I should hand them over to you,” the old man says.

“Don’t worry too much. I don’t want to make it too hard for you. At least, I have already prepared the necessary tools for you.”

Problem Description

For a positive integer $\alpha$, consider the following sequence $a$ of length $\alpha n$:

• For each $k = 1, \dots, n$, the sequence $a$ contains exactly $\alpha$ occurrences of $k$.

• For $i < j$ with $a_i = a_j$, for any $i < k < j$, we have $a_k \geq a_i$.

We call a sequence that satisfies the above requirements an $(n,\alpha)$-order permutation.

Now you are given an $(n_0,\alpha)$-order permutation $P$. You are also given $n$ and $m$. Please compute how many $(n,\alpha)$-order permutations contain $P$ as a subsequence, and also satisfy:

• There are exactly $m$ indices $i$ such that $a_i > a_{i+1}$.

You only need to output the result modulo $998244353$.

Input Format

The first line contains four integers $\alpha$, $n$, $m$, $n_0$.

The second line contains $\alpha n_0$ positive integers, which are guaranteed to form an $(n_0,\alpha)$-order permutation.

Output Format

Output one integer, the number of sequences that satisfy the requirements.

1 4 2 2
2 1

7

2 4 2 2
1 2 2 1

19

Hint

Constraints

Subtask 1 ($10$ points): $n \leq 2000$.

Subtask 2 ($10$ points): $\alpha = 1$, $n_0 = 1$.

Subtask 3 ($30$ points): $\alpha = 1$.

Subtask 4 ($15$ points): $\alpha = 2$, $n_0 = 1$.

Subtask 5 ($15$ points): $\alpha = 2$.

Subtask 6 ($20$ points): no special restrictions.

For all testdata, it is guaranteed that $1 \leq n \leq 2 \times 10^5$, $0 \leq m < n$, $1 \leq n_0 \leq n$, $1 \leq \alpha n_0 \leq 2 \times 10^5$.

Hint

To make it easier for contestants to handle formal power series computations, we provide a template. You may refer to and use this template as needed, or choose not to use it.

Translated by ChatGPT 5