AT_utpc2025_i Inversion Graph

整数 $ N,K $ と、長さ $ Q $ の整数列 $ D = (D_1, D_2, \dots, D_Q) $ が与えられます。 $ (1, 2, \dots, N) $ の順列 $ P = (P_1, P_2, \dots, P_N) $ に対して、頂点 $ 1 $ から頂点 $ N $ までの $ N $ 個の頂点を持つ無向グラフ $ G(P) $ を以下のように定義します。 > $ 1 \leq i < j \leq N $ を満たす整数の組 $ (i, j) $ について、 $ P_i > P_j $ であるとき、またそのときに限り、 $ G(P) $ において頂点 $ i $ と頂点 $ j $ の間に辺が存在する。 また、各 $ d = 1, 2, \dots, N-1 $ について、以下の条件を全て満たす $ (1, 2, \dots, N) $ の順列 $ P $ 全体の集合を $ \mathcal{S}_d $ とします。 - $ G(P) $ が木である。 - $ G(P) $ の直径が $ d $ である。 $ q = 1, 2, \dots, Q $ に対し、 $ \displaystyle \sum_{P \in \mathcal{S}_{D_q}} (\mathrm{LIS}(P))^K $ を $ 998244353 $ で割った余りを求めてください。ただし、 $ \mathrm{LIS}(P) $ は順列 $ P $ の最長増加部分列の長さを表します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ Q $ $ D_1 $ $ D_2 $ $ \vdots $ $ D_Q $

$ q = 1, 2, \dots, Q $ に対する答えをこの順に改行区切りで出力せよ。

### 部分点 - 追加の制約 $ N \le 500 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ G(P) $ が木であるような $ (1, 2, 3, 4) $ の順列 $ P $ は以下の $ 4 $ 通りです。 - $ P = (2, 3, 4, 1) $ ： $ G(P) $ の直径は $ 2 $ で、 $ \mathrm{LIS}(P) = 3 $ です。 - $ P = (4, 1, 2, 3) $ ： $ G(P) $ の直径は $ 2 $ で、 $ \mathrm{LIS}(P) = 3 $ です。 - $ P = (2, 4, 1, 3) $ ： $ G(P) $ の直径は $ 3 $ で、 $ \mathrm{LIS}(P) = 2 $ です。 - $ P = (3, 1, 4, 2) $ ： $ G(P) $ の直径は $ 3 $ で、 $ \mathrm{LIS}(P) = 2 $ です。 以上より - $ q = 1 $ に対する答えは $ 0 $ - $ q = 2 $ に対する答えは $ 3^0 + 3^0 = 2 $ - $ q = 3 $ に対する答えは $ 2^0 + 2^0 = 2 $ となります。 ### Constraints - 入力は全て整数 - $ 2 \leq N \leq 10^6 $ - $ 0 \leq K \leq 10^{18} $ - $ 1\le Q\le 2\times 10^5 $ - $ 1\le D_1 < D_2 < \ldots < D_Q < N $