AT_1202Contest_f.K-Medians Clustering

给定正整数 $ N,\ M,\ K $ 和长度为 $ K $ 的正整数序列 $ c=(c_1,\ c_2,\ \dots,\ c_K) $。
对于一个由不超过 $ M $ 的正整数组成的长度为 $ N $ 的多重集合 $ S $，如果存在 $ K $ 个多重集合 $ (S_1,\ S_2,\ \dots,\ S_K) $ 满足以下条件，则称该多重集合为好的多重集合：

• $ S_1,\ S_2,\ \dots,\ S_K $ 都不为空。
• 对于每个 $ i=1,\ 2,\ \dots,\ K $，$ S_i $ 的中位数是 $ c_i $。
• $ S_1,\ S_2,\ \dots,\ S_K $ 中的元素总数为 $ N $。由这 $ N $ 个元素组成的多重集合与 $ S $ 相等。

对于这个问题，多重集合 $ T $ 的中位数定义为将 $ T $ 的元素按升序排列后的第 $ \lceil\ n\ /\ 2\ \rceil $ 个元素。例如， $ T=\lbrace\ 1,\ 2,\ 3,\ 4\ \rbrace $ 的中位数是 $ 2 $， $ T=\lbrace\ 1,\ 3,\ 5,\ 7,\ 7\ \rbrace $ 的中位数是 $ 5 $。
请计算满足条件的好的多重集合的数量模 $ 998244353 $ 的余数。

输入以以下格式给出：

$ N\ M\ K $ $ c_1\ c_2\ \dots\ c_K $

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

约束

• $ 1\ \leq\ N,\ M\ \leq\ 10^7 $
• $ 1\ \leq\ K\ \leq\ \min(2\ \times\ 10^5,\ N) $
• $ 1\ \leq\ c_i\ \leq\ M $
• 输入皆为整数

Translate by @XYQ_102