Gegeben sind ganze Zahlen $N, K$ sowie eine ganzzahlige Folge $D = (D_1, D_2, \dots, D_Q)$ der Länge $Q$.

Für eine Permutation $P = (P_1, P_2, \dots, P_N)$ von $(1, 2, \dots, N)$ definieren wir einen ungerichteten Graphen $G(P)$ mit den Knoten $1, 2, \dots, N$ wie folgt:

Für jedes Paar ganzer Zahlen $(i, j)$ mit $1 \le i < j \le N$ gibt es in $G(P)$ genau dann eine Kante zwischen den Knoten $i$ und $j$, wenn $P_i > P_j$ gilt.

Für jedes $d = 1, 2, \dots, N - 1$ sei $\mathcal{S}_d$ die Menge aller Permutationen $P$ von $(1, 2, \dots, N)$, die alle folgenden Bedingungen erfüllen:

• $G(P)$ ist ein Baum.
• Der Durchmesser von $G(P)$ beträgt $d$.

Berechne für jede Anfrage $q = 1, 2, \dots, Q$

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

wobei $\text{LIS}(P)$ die Länge der längsten aufsteigenden Teilfolge von $P$ bezeichnet.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

N K
Q
D_1
D_2
:
D_Q

• Alle Eingabewerte sind ganze Zahlen.
• $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$

Ausgabe

Gib der Reihe nach $Q$ Zeilen aus.

Die $q$-te Zeile soll die Antwort für $q$ enthalten.

Beispiele

Beispieleingabe 1

4 0
3
1
2
3

Beispielausgabe 1

0
2
2

Beispieleingabe 2

2 100
1
1

Beispielausgabe 2

1

Beispieleingabe 3

314159 26535
5
271
828
1828
45904
52353

Beispielausgabe 3

765557189
351184939
258247317
305813889
68486796

Hinweis

Im ersten Beispiel sind die Permutationen $P$ von $(1, 2, 3, 4)$, für die $G(P)$ ein Baum ist, genau die folgenden $4$ Permutationen:

• $P = (2, 3, 4, 1)$: Der Durchmesser von $G(P)$ ist $2$, und $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: Der Durchmesser von $G(P)$ ist $2$, und $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: Der Durchmesser von $G(P)$ ist $3$, und $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: Der Durchmesser von $G(P)$ ist $3$, und $\text{LIS}(P) = 2$.

Daher gilt:

• Für $q = 1$ ist die Antwort $0$.
• Für $q = 2$ ist die Antwort $3^0 + 3^0 = 2$.
• Für $q = 3$ ist die Antwort $2^0 + 2^0 = 2$.