AT1202Contest_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 $ 的余数。

无

无

### 制約 - $ 1\ \leq\ N,\ M\ \leq\ 10^7 $ - $ 1\ \leq\ K\ \leq\ \min(2\ \times\ 10^5,\ N) $ - $ 1\ \leq\ c_i\ \leq\ M $ - 入力は全て整数 ### Sample Explanation 1 例えば $ S=\lbrace\ 1,1,1,2,3,4,5,5\ \rbrace $ は，条件を満たす $ (S_1,\ S_2,\ S_3) $ が次のように存在するため良い多重集合です． - $ S_1\ =\ \lbrace\ 1,\ \mathbf{4},\ 5\ \rbrace $ - $ S_2\ =\ \lbrace\ 1,\ \mathbf{1},\ 2,\ 3\ \rbrace $ - $ S_3\ =\ \lbrace\ \mathbf{5}\ \rbrace $