問題文

$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)$

入力例 1

3 4
1 1 2

出力例 1

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

2 1
1 1

出力例 2

0

入力例 3

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

出力例 3

30481920 257886720 199419134 838462446 196874334