Description

对于正整数 $\alpha$，考虑下述长为 $\alpha n$ 的序列 $a$：

• 对于每个 $k=1,\dots, n$，序列 $a$ 中出现了恰好 $\alpha$ 个 $k$。

• 对于 $i < j$ 满足 $a_i = a_j$，那么对任意 $i < k < j$，有 $a_k \geq a_i$。

我们称满足上述要求的序列是一个 $(n,\alpha)$ 阶排列。

现在输入一个 $(n_0,\alpha)$ 阶排列 $P$。又给定 $n$ 和 $m$，请你计算有多少 $(n,\alpha)$ 阶排列包含子序列 $P$，并且满足：

• 总共有 $m$ 个下标 $i$ 满足 $a_i > a_{i+1}$。

你只需计算出这样的序列总数对 $998244353$ 取模的结果。

Input Format

第一行输入四个整数 $\alpha$，$n$，$m$，$n_0$。

第二行输入 $\alpha n_0$ 个正整数，保证构成一个 $(n_0,\alpha)$ 阶排列。

Output Format

输出一个整数，表示满足要求的序列的数量。

1 4 2 2
2 1

7

2 4 2 2
1 2 2 1

19

Hint

【数据范围】

子任务 $1$（$10$ 分）：保证 $n \leq 2000$。

子任务 $2$（$10$ 分）：保证 $\alpha = 1$，$n_0=1$。

子任务 $3$（$30$ 分）：保证 $\alpha = 1$。

子任务 $4$（$15$ 分）：保证 $\alpha = 2$，$n_0=1$。

子任务 $5$（$15$ 分）：保证 $\alpha = 2$。

子任务 $6$（$20$ 分）：无特殊限制。

对于所有数据，保证 $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$。

【提示】

为了方便选手处理形式幂级数的运算，我们提供了一个模板。选手可以根据自己的需要参考与使用该模板，也可以不使用该模板。