P12053 [THUPC 2025 决赛] 对脑电波

你和他曾一起尝试过解决一道题目。 一道题目的解决方案可以看作从 $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 解释 以下为满足要求的 $4$ 种排列： $1,4,5,2,3$ $4,1,5,2,3$ $4,5,1,2,3$ $4,5,2,1,3$ ### 样例 #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 解释 显然无满足要求的排列。 ### 提示 Bonus: $n \leq 5000$。 ### 来源与致谢 来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 。