题目描述

给定正整数 $n,\ m,\ k$ 和长度为 $k$ 的正整数序列 $c=(c_1, c_2, \dots, c_k)$。

定义可重集 $T$ 的中位数为将 $T$ 的元素按从小到大排列后的第 $\lceil n / 2 \rceil$ 个元素。例如， $T=\lbrace 1, 2, 3, 4 \rbrace$ 的中位数是 $2$， $T=\lbrace 1, 3, 5, 7, 7 \rbrace$ 的中位数是 $5$。

对于一个由不超过 $m$ 的正整数组成的长度为 $n$ 的可重集 $S$，如果 $S$ 能被划分成 $k$ 个非空可重集，使得其中位数依次为 $c_1, c_2, \dots, c_k$，那么则称该集合 $S$ 是好的。

例如：当 $k=3,c_1=1,c_2=4,c_3=5,n=8,m=5$ 时，可重集 $\{1,1,1,4,4,5,5,5\}$ 是好的，因为它可以被划分成 $\{1,1,1,1,4\},\{4,5\},\{5\}$，也可以划分成 $\{1,1,4,5\},\{1,4,5\},\{5\}$。但是可重集 $\{1,2,2,2,2,2,4,5\}$ 不是好的，因为它不能被划分成任何三个中位数分别是 $1,4,5$ 的可重集。

请计算满足条件的好的可重集 $S$ 的数量模 998244353 的余数。

输入格式

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

第二行 $k$ 个正整数，第 $i$ 个为 $c_i$。

输出格式

输出满足条件的好的多重集合的数量模 998244353 的余数。

输入输出样例 #1

输入 #1

8 5 3
4 1 5

输出 #1

105

输入输出样例 #2

输入 #2

10000000 2 2
1 2

输出 #2

9999999

输入输出样例 #3

输入 #3

30 10 5
3 1 4 1 5

输出 #3

38446044

说明/提示

本题开启捆绑测试点与子任务依赖。

对于全部数据，$1\leq n,m\leq 10^7$，$1\leq k\leq\min(2\times 10^5, n)$，$1 \leq c_i \leq m$，输入皆为整数。