Bạn được cho các số nguyên $N, K$ và một dãy số nguyên $D = (D_1, D_2, \dots, D_Q)$ có độ dài $Q$.

Với một hoán vị $P = (P_1, P_2, \dots, P_N)$ của $(1, 2, \dots, N)$, ta định nghĩa một đồ thị vô hướng $G(P)$ gồm các đỉnh $1, 2, \dots, N$ như sau:

Với mỗi cặp số nguyên $(i, j)$ thỏa mãn $1 \le i < j \le N$, có một cạnh nối giữa hai đỉnh $i$ và $j$ trong $G(P)$ khi và chỉ khi $P_i > P_j$.

Với mỗi $d = 1, 2, \dots, N - 1$, gọi $\mathcal{S}_d$ là tập hợp tất cả các hoán vị $P$ của $(1, 2, \dots, N)$ thỏa mãn tất cả các điều kiện sau:

• $G(P)$ là một cây.
• Đường kính của $G(P)$ bằng $d$.

Với mỗi truy vấn $q = 1, 2, \dots, Q$, hãy tính

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

trong đó $\text{LIS}(P)$ ký hiệu độ dài của dãy con tăng dài nhất của $P$.

Dữ liệu vào

Dữ liệu vào được cung cấp từ Đầu vào chuẩn theo định dạng sau:

N K
Q
D_1
D_2
:
D_Q

• Tất cả các giá trị đầu vào đều là số nguyên.
• $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$

Kết quả

In ra $Q$ dòng theo thứ tự.

Dòng thứ $q$ chứa câu trả lời cho $q$.

Ví dụ

Ví dụ đầu vào 1

4 0
3
1
2
3

Ví dụ đầu ra 1

0
2
2

Ví dụ đầu vào 2

2 100
1
1

Ví dụ đầu ra 2

1

Ví dụ đầu vào 3

314159 26535
5
271
828
1828
45904
52353

Ví dụ đầu ra 3

765557189
351184939
258247317
305813889
68486796

Ghi chú

Ở ví dụ thứ nhất, các hoán vị $P$ của $(1, 2, 3, 4)$ sao cho $G(P)$ là một cây là đúng $4$ hoán vị sau:

• $P = (2, 3, 4, 1)$: đường kính của $G(P)$ là $2$, và $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: đường kính của $G(P)$ là $2$, và $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: đường kính của $G(P)$ là $3$, và $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: đường kính của $G(P)$ là $3$, và $\text{LIS}(P) = 2$.

Do đó:

• Với $q = 1$, câu trả lời là $0$.
• Với $q = 2$, câu trả lời là $3^0 + 3^0 = 2$.
• Với $q = 3$, câu trả lời là $2^0 + 2^0 = 2$.