נתונים מספרים שלמים $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$.