整数 $N, K$ および長さ $Q$ の整数列 $D = (D_1, D_2, \dots, D_Q)$ が与えられます。

$(1, 2, \dots, N)$ の順列 $P = (P_1, P_2, \dots, P_N)$ に対して、頂点 $1, 2, \dots, N$ をもつ無向グラフ $G(P)$ を次のように定義します：

$1 \le i < j \le N$ を満たす整数の組 $(i, j)$ それぞれについて、$G(P)$ において頂点 $i$ と頂点 $j$ の間に辺が存在するのは、$P_i > P_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$ について、次の値を求めてください：

$$\sum_{P \in \mathcal{S}_{D_q}} (\text{LIS}(P))^K \bmod 998244353,$$

ただし、$\text{LIS}(P)$ は $P$ の最長増加部分列の長さを表します。

入力

入力は以下の形式で標準入力から与えられます：

N K
Q
D_1
D_2
:
D_Q

• 入力される値はすべて整数である。
• $2 \le N \le 10^6$
• $0 \le K \le 10^{18}$
• $1 \le Q \le 2 \times 10^5$
• $1 \le D_1 < D_2 < \dots < D_Q < N$

出力

順に $Q$ 行出力してください。

$q$ 行目にはクエリ $q$ に対する答えを出力してください。

入出力例

入力例 1

4 0
3
1
2
3

出力例 1

0
2
2

入力例 2

2 100
1
1

出力例 2

1

入力例 3

314159 26535
5
271
828
1828
45904
52353

出力例 3

765557189
351184939
258247317
305813889
68486796

注記

1 つ目の例において、$G(P)$ が木となる $(1, 2, 3, 4)$ の順列 $P$ はちょうど以下の $4$ 個です：

• $P = (2, 3, 4, 1)$：$G(P)$ の直径は $2$ であり、$\text{LIS}(P) = 3$ です。
• $P = (4, 1, 2, 3)$：$G(P)$ の直径は $2$ であり、$\text{LIS}(P) = 3$ です。
• $P = (2, 4, 1, 3)$：$G(P)$ の直径は $3$ であり、$\text{LIS}(P) = 2$ です。
• $P = (3, 1, 4, 2)$：$G(P)$ の直径は $3$ であり、$\text{LIS}(P) = 2$ です。

したがって：

• $q = 1$ のとき、答えは $0$ です。
• $q = 2$ のとき、答えは $3^0 + 3^0 = 2$ です。
• $q = 3$ のとき、答えは $2^0 + 2^0 = 2$ です。