問題文

整数 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 の最長増加部分列の長さを表します。

制約

• 入力は全て整数
• 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

部分点

• 追加の制約 N \le 500 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

4 0
3
1
2
3

出力例 1

0
2
2

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

となります。

入力例 2

2 100
1
1

出力例 2

1

入力例 3

314159 26535
5
271
828
1828
45904
52353

出力例 3

765557189
351184939
258247317
305813889
68486796