UOJ Logo Universal Online Judge

UOJ

#788. 【CTS2023】另一个欧拉数问题

附件下载 统计

题目背景

你继续向前走,遇到了一个身着黑袍的老人,那边的门前放着一个巨大的沙盘,老人用手中的树枝在沙盘前画着奇怪的符号。

老人告诉你,他从年轻开始便梦想一个问题,直到他垂垂老矣,似乎也只揭露了答案的一角。

或许我该将它们交给你们了,老人说。

别太担心,我不想太为难你,至少我已经把必要的工具给你准备好了。

题目描述

对于正整数 $\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$ 取模的结果。

输入格式

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

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

输出格式

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

样例一

input

1 4 2 2
2 1

output

7

样例二

input

2 4 2 2
1 2 2 1

output

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$。

提示

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