Du får gitt heltallene $N, K$ og en heltallsfølge $D = (D_1, D_2, \dots, D_Q)$ med lengde $Q$.

For en permutasjon $P = (P_1, P_2, \dots, P_N)$ av $(1, 2, \dots, N)$ definerer vi en urettet graf $G(P)$ med noder $1, 2, \dots, N$ som følger:

For hvert par av heltall $(i, j)$ med $1 \le i < j \le N$ er det en kant mellom nodene $i$ og $j$ i $G(P)$ hvis og bare hvis $P_i > P_j$.

For hver $d = 1, 2, \dots, N - 1$, la $\mathcal{S}_d$ være mengden av alle permutasjoner $P$ av $(1, 2, \dots, N)$ som oppfyller alle de følgende betingelsene:

• $G(P)$ er et tre.
• Diameteren til $G(P)$ er $d$.

For hver spørring $q = 1, 2, \dots, Q$, beregn

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

der $\text{LIS}(P)$ betegner lengden på den lengste stigende delfølgen av $P$.

Inndata

Inndataene gis fra standard inndata på følgende format:

N K
Q
D_1
D_2
:
D_Q

• Alle inndataverdier er heltall.
• $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$ linjer i rekkefølge.

Den $q$-te linjen skal inneholde svaret for $q$.

Eksempler

Eksempelinndata 1

4 0
3
1
2
3

Eksempelutdata 1

0
2
2

Eksempelinndata 2

2 100
1
1

Eksempelutdata 2

1

Eksempelinndata 3

314159 26535
5
271
828
1828
45904
52353

Eksempelutdata 3

765557189
351184939
258247317
305813889
68486796

Merk

I det første eksempelet er permutasjonene $P$ av $(1, 2, 3, 4)$ slik at $G(P)$ er et tre nøyaktig de følgende $4$ permutasjonene:

• $P = (2, 3, 4, 1)$: diameteren til $G(P)$ er $2$, og $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: diameteren til $G(P)$ er $2$, og $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: diameteren til $G(P)$ er $3$, og $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: diameteren til $G(P)$ er $3$, og $\text{LIS}(P) = 2$.

Derfor:

• For $q = 1$ er svaret $0$.
• For $q = 2$ er svaret $3^0 + 3^0 = 2$.
• For $q = 3$ er svaret $2^0 + 2^0 = 2$.