题目背景
Вы продолжаете идти вперед и встречаете старика в черном балахоне. Перед дверью рядом с ним стоит огромный песочный стол, на котором старик чертит странные символы веткой, которую держит в руке.
Старик говорит вам, что с юности мечтал решить одну задачу, но даже дожив до глубокой старости, он, кажется, приоткрыл лишь малую часть ответа.
«Возможно, мне стоит передать их вам», — сказал старик.
«Не волнуйтесь, я не хочу слишком сильно вас затруднять, по крайней мере, я уже подготовил для вас необходимые инструменты».
Условие задачи
Для положительного целого числа $\alpha$ рассмотрим последовательность $a$ длины $\alpha n$, удовлетворяющую следующим условиям:
- Для каждого $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$.
Входные данные
В первой строке записаны четыре целых числа $\alpha$, $n$, $m$, $n_0$.
Во второй строке записаны $\alpha n_0$ положительных целых чисел, образующих $(n_0,\alpha)$-упорядоченную перестановку.
Выходные данные
Выведите одно целое число — количество последовательностей, удовлетворяющих условиям.
Примеры
Пример 1
1 4 2 2 2 1
Выходные данные 1
7
Пример 2
2 4 2 2 1 2 2 1
Выходные данные 2
19
Подзадачи
Для $10\%$ данных гарантируется $n \leq 2000$.
Для следующих $10\%$ данных гарантируется $\alpha = 1$, $n_0=1$.
Для следующих $30\%$ данных гарантируется $\alpha = 1$.
Для следующих $15\%$ данных гарантируется $\alpha = 2$, $n_0=1$.
Для следующих $15\%$ данных гарантируется $\alpha = 2$.
Для $100\%$ данных гарантируется $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$.
Примечание
Для удобства работы с операциями над формальными степенными рядами мы предоставляем шаблон. Участники могут использовать его по своему усмотрению или не использовать вовсе.