Вам даны целые числа $N, K$ и целочисленная последовательность $D = (D_1, D_2, \dots, D_Q)$ длины $Q$.

Для перестановки $P = (P_1, P_2, \dots, P_N)$ чисел $(1, 2, \dots, N)$ определим неориентированный граф $G(P)$ с вершинами $1, 2, \dots, N$ следующим образом:

Для каждой пары целых чисел $(i, j)$ с условием $1 \le i < j \le N$ ребро между вершинами $i$ и $j$ в $G(P)$ проводится тогда и только тогда, когда $P_i > P_j$.

Для каждого $d = 1, 2, \dots, N - 1$ обозначим через $\mathcal{S}_d$ множество всех перестановок $P$ чисел $(1, 2, \dots, N)$, удовлетворяющих всем следующим условиям:

• $G(P)$ является деревом.
• Диаметр графа $G(P)$ равен $d$.

Для каждого запроса $q = 1, 2, \dots, Q$ вычислите

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

где $\text{LIS}(P)$ обозначает длину наибольшей возрастающей подпоследовательности перестановки $P$.

Входные данные

Входные данные подаются из стандартного потока ввода в следующем формате:

N K
Q
D_1
D_2
:
D_Q

• Все входные значения — целые числа.
• $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$

Выходные данные

Выведите по порядку $Q$ строк.

В $q$-й строке должен содержаться ответ для $q$.

Примеры

Пример ввода 1

4 0
3
1
2
3

Пример вывода 1

0
2
2

Пример ввода 2

2 100
1
1

Пример вывода 2

1

Пример ввода 3

314159 26535
5
271
828
1828
45904
52353

Пример вывода 3

765557189
351184939
258247317
305813889
68486796

Примечание

В первом примере перестановками $P$ чисел $(1, 2, 3, 4)$, для которых $G(P)$ является деревом, являются ровно следующие $4$ перестановки:

• $P = (2, 3, 4, 1)$: диаметр $G(P)$ равен $2$, и $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: диаметр $G(P)$ равен $2$, и $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: диаметр $G(P)$ равен $3$, и $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: диаметр $G(P)$ равен $3$, и $\text{LIS}(P) = 2$.

Следовательно:

• При $q = 1$ ответ равен $0$.
• При $q = 2$ ответ равен $3^0 + 3^0 = 2$.
• При $q = 3$ ответ равен $2^0 + 2^0 = 2$.