Du får heltalen $N, K$ samt en heltalsföljd $D = (D_1, D_2, \dots, D_Q)$ av längd $Q$.

För en permutation $P = (P_1, P_2, \dots, P_N)$ av $(1, 2, \dots, N)$, definiera en oriktad graf $G(P)$ med hörn $1, 2, \dots, N$ enligt följande:

För varje par av heltal $(i, j)$ med $1 \le i < j \le N$ finns det en kant mellan hörnen $i$ och $j$ i $G(P)$ om och endast om $P_i > P_j$.

För varje $d = 1, 2, \dots, N - 1$, låt $\mathcal{S}_d$ vara mängden av alla permutationer $P$ av $(1, 2, \dots, N)$ som uppfyller alla följande villkor:

• $G(P)$ är ett träd.
• Diametern hos $G(P)$ är $d$.

För varje fråga $q = 1, 2, \dots, Q$, beräkna

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

där $\text{LIS}(P)$ betecknar längden på den längsta växande delföljden i $P$.

Indata

Indatan ges från standardinmatningen i följande format:

N K
Q
D_1
D_2
:
D_Q

• Alla indatavärden är heltal.
• $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$

Utdata

Skriv ut $Q$ rader i ordning.

Den $q$-te raden ska innehålla svaret för $q$.

Exempel

Exempelindata 1

4 0
3
1
2
3

Exempelutdata 1

0
2
2

Exempelindata 2

2 100
1
1

Exempelutdata 2

1

Exempelindata 3

314159 26535
5
271
828
1828
45904
52353

Exempelutdata 3

765557189
351184939
258247317
305813889
68486796

Förklaring

I det första exemplet är de permutationer $P$ av $(1, 2, 3, 4)$ sådana att $G(P)$ är ett träd exakt följande $4$ permutationer:

• $P = (2, 3, 4, 1)$: diametern hos $G(P)$ är $2$, och $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: diametern hos $G(P)$ är $2$, och $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: diametern hos $G(P)$ är $3$, och $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: diametern hos $G(P)$ är $3$, och $\text{LIS}(P) = 2$.

Därför:

• För $q = 1$ är svaret $0$.
• För $q = 2$ är svaret $3^0 + 3^0 = 2$.
• För $q = 3$ är svaret $2^0 + 2^0 = 2$.