给定整数 $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$ 取模。

2 2
2 2

1 6 6

图 $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$ 单调不减，特殊性质与分值如下表所示。

后 $4$ 个子任务满足序列 $A$ 单调不增，设 $b_i = \sum_{j=1}^n [a_j \geq i]$，特殊性质与分值如下表所示。

请注意算法常数对运行时间带来的影响。

时间限制：$\texttt{3s}$

空间限制：$\texttt{512MB}$

下载

样例数据下载