#P18007. Inversion Graph

Inversion Graph

Inversion Graph

给定整数 N,KN,K 及长度为 QQ 的严格递增整数序列 D=(D1,…,DQ)D=(D_1,\ldots,D_Q)。

对于 1,2,…,N1,2,\ldots,N 的一个排列 P=(P1,…,PN)P=(P_1,\ldots,P_N),定义无向图 G(P)G(P):顶点为 1,…,N1,\ldots,N,对于 i<ji<j,当且仅当 Pi>PjP_i>P_j 时,顶点 i,ji,j 之间有一条边。

令 SdS_d 表示满足以下两个条件的所有排列 PP 构成的集合:

  • G(P)G(P) 是一棵树。
  • G(P)G(P) 的直径为 dd。直径按路径上的边数计。

对每个询问 DqD_q,求

$$\sum_{P\in S_{D_q}}\operatorname{LIS}(P)^K\pmod{998244353},$$

其中 LIS⁡(P)\operatorname{LIS}(P) 是排列 PP 的最长严格递增子序列长度。

输入格式

第一行两个整数 N,KN,K。第二行一个整数 QQ。接下来 QQ 行,每行一个整数 DqD_q。

输出格式

输出 QQ 行,第 qq 行为对应询问的答案。

数据范围

2≤N≤1062\le N\le10^6,0≤K≤10180\le K\le10^{18},1≤Q≤2×1051\le Q\le2\times10^5,1≤D1<⋯<DQ<N1\le D_1<\cdots<D_Q<N。

样例 1

输入

4 0
3
1
2
3

输出

0
2
2

样例 2

输入

2 100
1
1

输出

1

样例 3

输入

314159 26535
5
271
828
1828
45904
52353

输出

765557189
351184939
258247317
305813889
68486796