AT1202Contest_f K-Medians Clustering

[problemUrl]: https://atcoder.jp/contests/DEGwer2023/tasks/1202Contest_f 正整数 $ 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 $ に等しい． ただしこの問題において，要素数 $ n\ (\geq\ 1) $ の多重集合 $ 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/A

N/A

### 制約 - $ 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 $