配点 : $600$ 点

問題文

$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)$ を列挙してください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$a_1$ $a_2$ $\dots$ $a_N$

出力

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

$F(1)$ $F(2)$ $\dots$ $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