给定整数 $n,y$ 和一个长度为 $n$ 的整数序列 $A = \{a_1,a_2,\cdots,a_n\}$，保证序列 $A$ 单调不减或单调不增。
构建有向图 $G(V,E)$，其中 $V = \{1,2,\cdots,n\}$，$E = \{(i,j) \mid 1 \leq i,j \leq n, a_i \geq j\}$。注意图 $G$ 中可能包含自环。
定义边子集 $T \subseteq E$ 合法当且仅当图 $G'(V,T)$ 中每个点的入度和出度不超过 $1$，自环对对应点的入度和出度均贡献 $1$。定义一个合法边子集 $T$ 的权值为 $y^{\mathrm{cycle}(T)}$，其中 $\mathrm{cycle}(T)$ 表示图 $G'(V,T)$ 的环数，自环是一个环。
特别地，本题认为 $0^0=1$。
对于所有整数 $0 \leq k \leq n$，求所有大小为 $k$ 的合法边子集的权值和，对 $998244353$ 取模。
输入格式
第一行两个整数 $n,y$，第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 描述序列 $A$。
输出格式
一行 $n+1$ 个整数，第 $i$ 个整数表示大小为 $i-1$ 的合法边子集的权值和，对 $998244353$ 取模。
样例一
input
2 2 2 2
output
1 6 6
explanation
图 $G$ 中有两个点和边 $\{(1,1),(1,2),(2,1),(2,2)\}$。
大小为 $0$ 的合法边子集仅有空集，其权值为 $1$，故大小为 $0$ 的合法边子集的权值和为 $1$；
大小为 $1$ 的合法边子集有 $\{(1,1)\},\{(2,2)\},\{(1,2)\},\{(2,1)\}$，它们的权值分别为 $2,2,1,1$，权值和为 $6$；
大小为 $2$ 的合法边子集有 $\{(1,1),(2,2)\},\{(1,2),(2,1)\}$，它们的权值分别为 $4,2$，权值和为 $6$。
限制与约定
对于 $100\%$ 的数据，$1 \leq n \leq 10^5 , 0 \leq y < 998244353 , 0 \leq a_i \leq n$。保证序列 $A$ 是单调不减或单调不增序列。
前 $5$ 个子任务满足序列 $A$ 单调不减，特殊性质与分值如下表所示。
| 子任务编号 | $n \leq $ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $8$ | 无 | $1$ |
| $2$ | $15$ | $y=0$ | $9$ |
| $3$ | $2000$ | 无 | $10$ |
| $4$ | $75000$ | $y=1$ | $15$ |
| $5$ | $10^5$ | 无 | $15$ |
后 $4$ 个子任务满足序列 $A$ 单调不增，设 $b_i = \sum_{j=1}^n [a_j \geq i]$，特殊性质与分值如下表所示。
| 子任务编号 | $n \leq $ | 特殊性质 | 分值 |
|---|---|---|---|
| $6$ | $15$ | $y=0$ | $5$ |
| $7$ | $2000$ | 无 | $10$ |
| $8$ | $75000$ | 对于所有满足 $a_i \geq i$ 的 $i$，$a_i \geq b_i$ | $15$ |
| $9$ | $10^5$ | 无 | $20$ |
请注意算法常数对运行时间带来的影响。
时间限制：$\texttt{3s}$
空间限制：$\texttt{512MB}$
鄂公网安备 42010202000505 号