给定整数 $N,K$ 和长度为 $Q$ 的整数序列 $D = (D_1, D_2, \dots, D_Q)$。

对于 $(1, 2, \dots, N)$ 的一个排列 $P = (P_1, P_2, \dots, P_N)$，如下定义一个包含 $N$ 个顶点（顶点编号为 $1$ 到 $N$）的无向图 $G(P)$：

对于所有满足 $1 \leq i < j \leq N$ 的整数对 $(i,j)$，当且仅当 $P_i > P_j$ 时，在 $G(P)$ 中顶点 $i$ 和顶点 $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$，请计算 $\displaystyle \sum_{P \in \mathcal{S}_{D_q}} (\mathrm{LIS}(P))^K$ 模 $998244353$ 的值。其中，$\mathrm{LIS}(P)$ 表示排列 $P$ 的最长递增子序列的长度。

输入从标准输入按以下格式给出：

$N$ $K$ $Q$ $D_1$ $D_2$ $\vdots$ $D_Q$

请按顺序，每行输出一个答案，共 $Q$ 行。

部分分

• 若对满足额外限制 $N \le 500$ 的数据集作答正确，可获得 $10$ 分。

样例解释 1

满足 $G(P)$ 是树的 $(1,2,3,4)$ 的排列 $P$ 共 $4$ 种：

• $P = (2, 3, 4, 1)$：$G(P)$ 的直径为 $2$，$\mathrm{LIS}(P) = 3$。
• $P = (4, 1, 2, 3)$：$G(P)$ 的直径为 $2$，$\mathrm{LIS}(P) = 3$。
• $P = (2, 4, 1, 3)$：$G(P)$ 的直径为 $3$，$\mathrm{LIS}(P) = 2$。
• $P = (3, 1, 4, 2)$：$G(P)$ 的直径为 $3$，$\mathrm{LIS}(P) = 2$。

因此：

• $q = 1$ 的答案为 $0$；
• $q = 2$ 的答案为 $3^0 + 3^0 = 2$；
• $q = 3$ 的答案为 $2^0 + 2^0 = 2$。

数据范围

• 所有输入均为整数
• $2 \leq N \leq 10^6$
• $0 \leq K \leq 10^{18}$
• $1 \le Q \le 2 \times 10^5$
• $1 \le D_1 < D_2 < \ldots < D_Q < N$

由 ChatGPT 5 翻译