给定整数 $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\le i,j\le n,a_i\ge j\}$。注意图 $G$ 中可能包含自环。

定义边子集 $T\subseteq E$ 合法当且仅当图 $G^{\prime }(V,T)$ 中每个点的入度和出度不超过 $1$，自环对对应点的入度和出度均贡献 $1$。定义一个合法边子集 $T$ 的权值为 $y^{\mathrm{cycle}(T)}$，其中 $\mathrm{cycle}(T)$ 表示图 $G^{\prime }(V,T)$ 的环数，自环是一个环。

特别地，本题认为 $0^0=1$。

对于所有整数 $0\le k\le 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\mathrm{\%}$ 的数据，$1\le n\le {10}^5,0\le y<998244353,0\le a_i\le n$。保证序列 $A$ 是单调不减或单调不增序列。

前 $5$ 个子任务满足序列 $A$ 单调不减，特殊性质与分值如下表所示。

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

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

时间限制：$\mathtt{\text{3s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载