Anda diberikan bilangan bulat $N, K$, serta sebuah barisan bilangan bulat $D = (D_1, D_2, \dots, D_Q)$ dengan panjang $Q$.

Untuk sebuah permutasi $P = (P_1, P_2, \dots, P_N)$ dari $(1, 2, \dots, N)$, definisikan sebuah graf tak berarah $G(P)$ dengan simpul $1, 2, \dots, N$ sebagai berikut:

Untuk setiap pasangan bilangan bulat $(i, j)$ dengan $1 \le i < j \le N$, terdapat sebuah sisi antara simpul $i$ dan $j$ di $G(P)$ jika dan hanya jika $P_i > P_j$.

Untuk setiap $d = 1, 2, \dots, N - 1$, misalkan $\mathcal{S}_d$ adalah himpunan semua permutasi $P$ dari $(1, 2, \dots, N)$ yang memenuhi semua kondisi berikut:

• $G(P)$ adalah sebuah pohon.
• Diameter dari $G(P)$ adalah $d$.

Untuk setiap kueri $q = 1, 2, \dots, Q$, hitunglah

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

di mana $\text{LIS}(P)$ menyatakan panjang dari upabarisan naik terpanjang (longest increasing subsequence) dari $P$.

Masukan

Masukan diberikan dari Masukan Standar dalam format berikut:

N K
Q
D_1
D_2
:
D_Q

• Semua nilai masukan adalah bilangan bulat.
• $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$

Keluaran

Cetak $Q$ baris secara berurutan.

Baris ke-$q$ harus berisi jawaban untuk $q$.

Contoh

Contoh Masukan 1

4 0
3
1
2
3

Contoh Keluaran 1

0
2
2

Contoh Masukan 2

2 100
1
1

Contoh Keluaran 2

1

Contoh Masukan 3

314159 26535
5
271
828
1828
45904
52353

Contoh Keluaran 3

765557189
351184939
258247317
305813889
68486796

Catatan

Pada contoh pertama, permutasi $P$ dari $(1, 2, 3, 4)$ sedemikian sehingga $G(P)$ merupakan sebuah pohon adalah tepat $4$ permutasi berikut:

• $P = (2, 3, 4, 1)$: diameter dari $G(P)$ adalah $2$, dan $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: diameter dari $G(P)$ adalah $2$, dan $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: diameter dari $G(P)$ adalah $3$, dan $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: diameter dari $G(P)$ adalah $3$, dan $\text{LIS}(P) = 2$.

Oleh karena itu:

• Untuk $q = 1$, jawabannya adalah $0$.
• Untuk $q = 2$, jawabannya adalah $3^0 + 3^0 = 2$.
• Untuk $q = 3$, jawabannya adalah $2^0 + 2^0 = 2$.