4280. [THUPC 2025 Final] 对脑电波

【题目描述】

你和他曾一起尝试过解决一道题目。

一道题目的解决方案可以看作从 $1$ 到 $n$ 编号的 $n$ 个性质。每个性质都可以通过一个特点 $p_i$ 来代表，$p_i$ 越大说明这个性质越智力，$p_i$ 越小表示这个性质越套路。由于每个性质都不完全相同，因此 $p$ 组成了一个长度为 $n$ 的排列。

他是日本题领域大神。他经过思考想出了 $k$ 个性质，这 $k$ 个性质组成的子序列 $S_0$ 恰好是 $p$ 的所有长度为 $k$ 的子序列中字典序最大的那个。

你是中国题领域大神。你经过思考也想出了 $k$ 个性质，这 $k$ 个性质组成的子序列 $S_1$ 恰好是 $p$ 的所有长度为 $k$ 的子序列中字典序最小的那个。

你们把你们思考出的性质分别罗列。你们在一张纸条上记录下了 $S_0$ 和 $S_1$ 之间的某一个最长公共子序列。

这时下课铃响了，你们一起去吃饭了。

后来过去了好久啊，你们也早已分道扬镳。在某一天，你在整理物品的时候又发现了这张纸条。你又想起了这道没能解决的难题。你想知道，当年的那道题目，有多少种可能的解决方案，最终可能会导致这张纸条的出现。

答案对 $998244353$ 取模。

【输入格式】

第一行包括三个正整数 $n,k,m\ (2\leq m\leq k\leq n\leq 400)$，分别表示题目性质的总数量、你和他找出的性质的数量和最长公共子序列的长度。

第二行包括 $m$ 个正整数 $S_1,S_2,\cdots,S_m\ (1 \leq S_i \leq n)$，表示记录在纸条上的最长公共子序列。

【输出格式】

输出一行一个整数，表示满足要求的排列数量对 $998244353$ 取模后的结果。

【输入样例 1】

5 3 2
2 3

【输出样例 1】

4

【样例 1 解释】

以下为满足要求的 $4$ 种排列：

$1,4,5,2,3$

$4,1,5,2,3$

$4,5,1,2,3$

$4,5,2,1,3$

【输入样例 2】

6 4 2
2 3

【输出样例 2】

10

【样例 2 解释】

以下为满足要求的 $10$ 种排列：

$1,4,5,6,2,3$

$1,4,6,5,2,3$

$1,5,4,6,2,3$

$1,6,4,5,2,3$

$4,6,5,1,2,3$

$4,6,5,2,1,3$

$5,1,4,6,2,3$

$6,1,4,5,2,3$

$6,4,5,1,2,3$

$6,4,5,2,1,3$

【输入样例 3】

2 2 2
1 1

【输出样例 3】

0

【样例解释 3】

显然无满足要求的排列。

【输入样例 4】

11 5 2
6 4

【输出样例 4】

198198

【输入样例 5】

20 10 5
13 17 10 6 5

【输出样例 5】

392592366