题面 样例

题目描述

给出一个长度为 $k$ 的序列 $a_1,a_2,...,a_k$。一个大小为 $n$，元素为 $[1,m]$ 之间正整数的多重集 $S$ 合法当且仅当：其可以被划分为 $k$ 个非空可重集 $S_1,S_2,...,S_k$，并且满足 $S_i$ 的中位数是 $a_i$。你需要计算合法多重集数量模 $998244353$ 的结果。

这里，我们定义一个大小为 $n$ 的多重集的中位数是其第 $\lceil \frac{n}{2} \rceil$ 小的数。

输入格式

第一行三个正整数 $n,m,k$。

接下来一行 $k$ 个正整数 $a_1,a_2,...,a_k$。

输出格式

一行一个整数表示答案。

样例输入 1

8 5 3
4 1 5

样例输出 1

105

样例输入 2

30 10 5
3 1 4 1 5

样例输出 2

38446044

数据范围

对于全部数据，满足 $n,m\le 5\times 10^6,k\le n,1\le c_i\le m$。

对于测试点 $1\sim 2$，满足 $n\le 5,m\le 3$。

对于测试点 $3\sim 4$，满足 $n,m\le 50,k=1$。

对于测试点 $5\sim 10$，满足 $n,m\le 50,k\le 3$。

对于测试点 $11\sim 15$，满足 $n,m\le 2000$。

对于测试点 $16\sim 18$，满足 $n,m\le 10^5$。

对于测试点 $19\sim 20$，无特殊限制。