色彩丰富度

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的球。球 $i$ 被涂上了颜色 $a_i$。

对于 $(1, 2, \dots, N)$ 的一个排列 $P = (P_1, P_2, \dots, P_N)$,我们如下定义 $C(P)$:

将球 $P_1, P_2, \dots, P_N$ 按此顺序排成一排时,颜色不同的相邻球对的个数。

设 $S_N$ 为 $(1, 2, \dots, N)$ 的所有排列构成的集合。另外,定义 $F(k)$ 为:

[ F(k) = \left( \sum_{P \in S_N} C(P)^k \right) \bmod 998244353 ]

请枚举 $F(1), F(2), \dots, F(M)$。

输入格式

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

N M
a_1 a_2 … a_N

输出格式

按以下格式输出答案:

F(1) F(2) … F(M)

样例

3 4
1 1 2

8 12 20 36

所有可能的 $(P, C(P))$ 对列表如下。

如果 $P=(1,2,3)$,则 $C(P) = 1$。

如果 $P=(1,3,2)$,则 $C(P) = 2$。

如果 $P=(2,1,3)$,则 $C(P) = 1$。

如果 $P=(2,3,1)$,则 $C(P) = 2$。

如果 $P=(3,1,2)$,则 $C(P) = 1$。

如果 $P=(3,2,1)$,则 $C(P) = 1$。

把这些值代入 $F(k)$ 即可得到答案。例如,$F(1) = 1^1 + 2^1 + 1^1 + 2^1 + 1^1 + 1^1 = 8$。

2 1
1 1

0

10 5
3 1 4 1 5 9 2 6 5 3

30481920 257886720 199419134 838462446 196874334

数据范围

• $2 \le N \le 2.5 \times 10^5$
• $1 \le M \le 2.5 \times 10^5$
• $1 \le a_i \le N$
• 输入中的所有值均为整数。