Background

You continue walking forward and encounter an old man in a black robe. In front of a door nearby, there is a giant sandbox, and the old man is drawing strange symbols in it with a branch.

The old man tells you that he has dreamed of a problem since he was young, and even now, in his old age, he seems to have only uncovered a corner of the answer.

"Perhaps I should pass them on to you," the old man says.

"Don't worry too much; I don't want to make it too difficult for you. At least I have already prepared the necessary tools for you."

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 any $i < j$ such that $a_i = a_j$, for any $i < k < j$, we have $a_k \geq a_i$.

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

Given an $(n_0, \alpha)$-order permutation $P$, as well as $n$ and $m$, calculate how many $(n, \alpha)$-order permutations contain $P$ as a subsequence and satisfy the following condition:

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

You only need to calculate the total number of such sequences modulo $998244353$.

Input

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

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

Output

Output a single integer representing the number of sequences that satisfy the requirements.

Examples

Input 1

1 4 2 2
2 1

Output 1

7

Input 2

2 4 2 2
1 2 2 1

Output 2

19

Subtasks

For $10\%$ of the data, $n \leq 2000$.

For another $10\%$ of the data, $\alpha = 1$ and $n_0 = 1$.

For another $30\%$ of the data, $\alpha = 1$.

For another $15\%$ of the data, $\alpha = 2$ and $n_0 = 1$.

For another $15\%$ of the data, $\alpha = 2$.

For $100\%$ of the data, $1 \leq n \leq 2 \times 10^5$, $0 \leq m < n$, $1 \leq n_0 \leq n$, and $1 \leq \alpha n_0 \leq 2 \times 10^5$.

Note

To assist participants in handling formal power series operations, we provide a template. Participants may refer to and use this template according to their needs, or they may choose not to use it.