Gefnar eru heiltölurnar $N, K$ og heiltöluruna $D = (D_1, D_2, \dots, D_Q)$ af lengd $Q$.

Fyrir umröðun $P = (P_1, P_2, \dots, P_N)$ á $(1, 2, \dots, N)$ skilgreinum við óstefnt net $G(P)$ með hnútum $1, 2, \dots, N$ sem hér segir:

Fyrir hvert par heiltalna $(i, j)$ með $1 \le i < j \le N$ er leggur á milli hnúta $i$ og $j$ í $G(P)$ ef og aðeins ef $P_i > P_j$.

Fyrir hvert $d = 1, 2, \dots, N - 1$, látum $\mathcal{S}_d$ vera mengi allra umraðana $P$ á $(1, 2, \dots, N)$ sem uppfylla öll eftirfarandi skilyrði:

• $G(P)$ er tré.
• Þvermál $G(P)$ er $d$.

Fyrir hverja fyrirspurn $q = 1, 2, \dots, Q$ skaltu reikna

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

þar sem $\text{LIS}(P)$ táknar lengd lengstu vaxandi hlutrunu í $P$.

Inntak

Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:

N K
Q
D_1
D_2
:
D_Q

• Öll inntaksgildi eru heiltölur.
• $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$

Úttak

Prentaðu $Q$ línur í röð.

Lína $q$ á að innihalda svarið fyrir $q$.

Dæmi

Dæmi um inntak 1

4 0
3
1
2
3

Dæmi um úttak 1

0
2
2

Dæmi um inntak 2

2 100
1
1

Dæmi um úttak 2

1

Dæmi um inntak 3

314159 26535
5
271
828
1828
45904
52353

Dæmi um úttak 3

765557189
351184939
258247317
305813889
68486796

Athugasemd

Í fyrsta dæminu eru umraðanirnar $P$ á $(1, 2, 3, 4)$ þannig að $G(P)$ sé tré nákvæmlega eftirfarandi $4$ umraðanir:

• $P = (2, 3, 4, 1)$: þvermál $G(P)$ er $2$, og $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: þvermál $G(P)$ er $2$, og $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: þvermál $G(P)$ er $3$, og $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: þvermál $G(P)$ er $3$, og $\text{LIS}(P) = 2$.

Þess vegna:

• Fyrir $q = 1$ er svarið $0$.
• Fyrir $q = 2$ er svarið $3^0 + 3^0 = 2$.
• Fyrir $q = 3$ er svarið $2^0 + 2^0 = 2$.