정수 $N, K$와 길이가 $Q$인 정수 수열 $D = (D_1, D_2, \dots, D_Q)$가 주어집니다.

$(1, 2, \dots, N)$의 순열 $P = (P_1, P_2, \dots, P_N)$에 대하여, 정점 $1, 2, \dots, N$을 갖는 무방향 그래프 $G(P)$를 다음과 같이 정의합니다:

$1 \le i < j \le N$을 만족하는 각 정수 쌍 $(i, j)$에 대해, $G(P)$에서 정점 $i$와 정점 $j$ 사이에 간선이 존재하는 것은 $P_i > P_j$인 것과 필요충분조건입니다.

각 $d = 1, 2, \dots, N - 1$에 대하여, $\mathcal{S}_d$를 다음 조건을 모두 만족하는 $(1, 2, \dots, N)$의 모든 순열 $P$의 집합이라고 합시다:

• $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

노트

첫 번째 예제에서, $G(P)$가 트리가 되도록 하는 $(1, 2, 3, 4)$의 순열 $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$입니다.