Annettuna ovat kokonaisluvut $N, K$ sekä pituutta $Q$ oleva kokonaislukujono $D = (D_1, D_2, \dots, D_Q)$.

Lukujen $(1, 2, \dots, N)$ permutaatiolle $P = (P_1, P_2, \dots, P_N)$ määritellään suuntaamaton verkko $G(P)$, jonka solmut ovat $1, 2, \dots, N$, seuraavasti:

Jokaiselle kokonaislukuparille $(i, j)$, jolle $1 \le i < j \le N$, verkossa $G(P)$ on kaari solmujen $i$ ja $j$ välillä jos ja vain jos $P_i > P_j$.

Jokaiselle $d = 1, 2, \dots, N - 1$ olkoon $\mathcal{S}_d$ kaikkien sellaisten lukujen $(1, 2, \dots, N)$ permutaatioiden $P$ joukko, jotka täyttävät kaikki seuraavat ehdot:

• $G(P)$ on puu.
• Verkon $G(P)$ halkaisija on $d$.

Laske jokaiselle kyselylle $q = 1, 2, \dots, Q$

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

missä $\text{LIS}(P)$ tarkoittaa permutaation $P$ pisimmän kasvavan alijonon pituutta.

Syöte

Syöte annetaan vakiosyötteestä seuraavassa muodossa:

N K
Q
D_1
D_2
:
D_Q

• Kaikki syötteen arvot ovat kokonaislukuja.
• $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$

Tuloste

Tulosta $Q$ riviä järjestyksessä.

Rivin $q$ tulee sisältää vastaus kyselyyn $q$.

Esimerkit

Esimerkkisyöte 1

4 0
3
1
2
3

Esimerkkituloste 1

0
2
2

Esimerkkisyöte 2

2 100
1
1

Esimerkkituloste 2

1

Esimerkkisyöte 3

314159 26535
5
271
828
1828
45904
52353

Esimerkkituloste 3

765557189
351184939
258247317
305813889
68486796

Huomautus

Ensimmäisessä esimerkissä lukujen $(1, 2, 3, 4)$ permutaatiot $P$, joilla $G(P)$ on puu, ovat täsmälleen seuraavat $4$ permutaatiota:

• $P = (2, 3, 4, 1)$: verkon $G(P)$ halkaisija on $2$, ja $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: verkon $G(P)$ halkaisija on $2$, ja $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: verkon $G(P)$ halkaisija on $3$, ja $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: verkon $G(P)$ halkaisija on $3$, ja $\text{LIS}(P) = 2$.

Näin ollen:

• Kun $q = 1$, vastaus on $0$.
• Kun $q = 2$, vastaus on $3^0 + 3^0 = 2$.
• Kun $q = 3$, vastaus on $2^0 + 2^0 = 2$.