On vous donne des entiers $N, K$ ainsi qu'une séquence d'entiers $D = (D_1, D_2, \dots, D_Q)$ de longueur $Q$.

Pour une permutation $P = (P_1, P_2, \dots, P_N)$ de $(1, 2, \dots, N)$, on définit un graphe non orienté $G(P)$ ayant pour sommets $1, 2, \dots, N$ de la façon suivante :

Pour chaque couple d'entiers $(i, j)$ tel que $1 \le i < j \le N$, il existe une arête entre les sommets $i$ et $j$ dans $G(P)$ si et seulement si $P_i > P_j$.

Pour chaque $d = 1, 2, \dots, N - 1$, soit $\mathcal{S}_d$ l'ensemble de toutes les permutations $P$ de $(1, 2, \dots, N)$ qui satisfont toutes les conditions suivantes :

• $G(P)$ est un arbre.
• Le diamètre de $G(P)$ est $d$.

Pour chaque requête $q = 1, 2, \dots, Q$, calculez

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

où $\text{LIS}(P)$ désigne la longueur de la plus longue sous-séquence strictement croissante de $P$.

Entrée

L'entrée est donnée depuis l'entrée standard dans le format suivant :

N K
Q
D_1
D_2
:
D_Q

• Toutes les valeurs d'entrée sont des entiers.
• $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$

Sortie

Affichez $Q$ lignes dans l'ordre.

La $q$-ème ligne doit contenir la réponse pour $q$.

Exemples

Exemple d'entrée 1

4 0
3
1
2
3

Exemple de sortie 1

0
2
2

Exemple d'entrée 2

2 100
1
1

Exemple de sortie 2

1

Exemple d'entrée 3

314159 26535
5
271
828
1828
45904
52353

Exemple de sortie 3

765557189
351184939
258247317
305813889
68486796

Note

Dans le premier exemple, les permutations $P$ de $(1, 2, 3, 4)$ telles que $G(P)$ soit un arbre sont exactement les $4$ permutations suivantes :

• $P = (2, 3, 4, 1)$ : le diamètre de $G(P)$ est $2$, et $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$ : le diamètre de $G(P)$ est $2$, et $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$ : le diamètre de $G(P)$ est $3$, et $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$ : le diamètre de $G(P)$ est $3$, et $\text{LIS}(P) = 2$.

Par conséquent :

• Pour $q = 1$, la réponse est $0$.
• Pour $q = 2$, la réponse est $3^0 + 3^0 = 2$.
• Pour $q = 3$, la réponse est $2^0 + 2^0 = 2$.