Se te dan los enteros $N, K$ y una secuencia de enteros $D = (D_1, D_2, \dots, D_Q)$ de longitud $Q$.
Para una permutación $P = (P_1, P_2, \dots, P_N)$ de $(1, 2, \dots, N)$, definimos un grafo no dirigido $G(P)$ con vértices $1, 2, \dots, N$ de la siguiente manera:
Para cada par de enteros $(i, j)$ con $1 \le i < j \le N$, hay una arista entre los vértices $i$ y $j$ en $G(P)$ si y solo si $P_i > P_j$.
Para cada $d = 1, 2, \dots, N - 1$, sea $\mathcal{S}_d$ el conjunto de todas las permutaciones $P$ de $(1, 2, \dots, N)$ que cumplen todas las condiciones siguientes:
- $G(P)$ es un árbol.
- El diámetro de $G(P)$ es $d$.
Para cada consulta $q = 1, 2, \dots, Q$, calcula
$$\sum_{P \in \mathcal{S}_{D_q}} (\text{LIS}(P))^K \bmod 998244353,$$
donde $\text{LIS}(P)$ denota la longitud de la subsecuencia creciente más larga de $P$.
Entrada
La entrada se proporciona desde la Entrada Estándar en el siguiente formato:
N K Q D_1 D_2 : D_Q
- Todos los valores de entrada son enteros.
- $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$
Salida
Imprime $Q$ líneas en orden.
La $q$-ésima línea debe contener la respuesta para $q$.
Ejemplos
Entrada de ejemplo 1
4 0 3 1 2 3
Salida de ejemplo 1
0 2 2
Entrada de ejemplo 2
2 100 1 1
Salida de ejemplo 2
1
Entrada de ejemplo 3
314159 26535 5 271 828 1828 45904 52353
Salida de ejemplo 3
765557189 351184939 258247317 305813889 68486796
Nota
En el primer ejemplo, las permutaciones $P$ de $(1, 2, 3, 4)$ tales que $G(P)$ es un árbol son exactamente las siguientes $4$ permutaciones:
- $P = (2, 3, 4, 1)$: el diámetro de $G(P)$ es $2$, y $\text{LIS}(P) = 3$.
- $P = (4, 1, 2, 3)$: el diámetro de $G(P)$ es $2$, y $\text{LIS}(P) = 3$.
- $P = (2, 4, 1, 3)$: el diámetro de $G(P)$ es $3$, y $\text{LIS}(P) = 2$.
- $P = (3, 1, 4, 2)$: el diámetro de $G(P)$ es $3$, y $\text{LIS}(P) = 2$.
Por lo tanto:
- Para $q = 1$, la respuesta es $0$.
- Para $q = 2$, la respuesta es $3^0 + 3^0 = 2$.
- Para $q = 3$, la respuesta es $2^0 + 2^0 = 2$.