AT_abc260_h [ABC260Ex] Colorfulness

[problemUrl]: https://atcoder.jp/contests/abc260/tasks/abc260_h $ 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) $

### 制約 - $ 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 $ です。