กำหนดจำนวนเต็ม $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$