题目描述

$1$ から $N$ までの番号がついた $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$ という順番に一列に並べたときの、異なる色のボールが隣り合っている場所の数。

$(1,\ 2,\ \dots,\ N)$ を並べ替えた列全体の集合を $S_N$ と置きます。また、$F(k)$ を次のように置きます。

$ \displaystyle\ 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$ $\dots$ $a_N$

输出格式

答えを以下の形式で出力せよ。

$F(1)$ $F(2)$ $\dots$ $F(M)$

题目大意

题目描述

给定 $n$ 个小球，第 $i$ 个小球上有一个数 $a_i$。

将小球按照任意顺序排列，定义分值为相邻两个小球数不同的对数。

对于每一个 $k \in [1, m]$，求对于所有排列小球的方案中，分值的 $k$ 次方的和，对 $998244353$ 取模。

输入格式

第一行两个整数 $n, m$。

第二行 $n$ 个整数，表示数组 $a$。

输出格式

一行 $m$ 个整数，表示答案。

3 4
1 1 2

8 12 20 36

2 1
1 1

0

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

30481920 257886720 199419134 838462446 196874334

提示

制約

• $2\ \leq\ N\ \leq\ 2.5\ \times\ 10^5$
• $1\ \leq\ M\ \leq\ 2.5\ \times\ 10^5$
• $1\ \leq\ a_i\ \leq\ N$
• 入力される値はすべて整数

Sample Explanation 1

$(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 $ です。