题目描述

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

一道题目的解决方案可以看作从 $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$ 取模后的结果。

5 3 2
2 3

4

6 4 2
2 3

10

2 2 2
1 1

0

11 5 2
6 4

198198

20 10 5
13 17 10 6 5

392592366

提示

样例 #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 官方仓库 https://thusaac.com/public。