[ABC249Ex] Dye Color

有 $n$ 个球，编号 $1\sim n$，初始时球 $i$ 的颜色为 $A_i$。颜色为 $1\sim n$ 的整数。 进行以下操作若干次，直到所有球颜色相同： * 均匀随机地选择一个球 $1\sim n$ 的子集（可以为空），记该集合中的球的编号为 $X_1,X_2,\cdots,X_k$。 * 均匀随机地选择一个长为 $k$ 的数列，其中每个元素为 $1\sim n$ 中的一个数，且两两不同，记这个数列为 $P_1,P_2,\cdots,P_k$。 * $\forall 1\le i\le k$，将球 $X_i$ 染成颜色 $P_i$。 求操作次数的期望对 $998244353$ 取模后的值。

[problemUrl]: https://atcoder.jp/contests/abc249/tasks/abc249_h $ N $ 個のボールがあり、ボールには $ 1 $ から $ N $ の番号がついています。初め、ボール $ i $ は色 $ A_i $ で塗られています。 色は $ 1 $ 以上 $ N $ 以下の整数によって表されます。 以下の操作を、全てのボールの色が等しくなるまで繰り返します。 - $ N $ 個のボールからなる集合の部分集合(空集合を含む)は $ 2^N $ 個あるが、そこから $ 1 $ 個の集合を一様ランダムに選ぶ。選んだ集合に含まれるボールの index を昇順に $ X_1,X_2,...,X_K $ とする。次に、$ (1,2,\dots,N) $ から $ K $ 個を選んで得られる順列を一様ランダムに $ 1 $ 個選び $ P=(P_1,P_2,\dots,P_K) $ とする。そして、$ 1\ \le\ i\ \le\ K $ を満たす整数 $ i $ に対し、ボール $ X_i $ の色を $ P_i $ に変更する。 操作回数の期待値 $ \bmod\ 998244353 $ を求めてください。 ここで、$ (1,2,\dots,N) $ から $ K $ 個を選んで得られる順列とは、$ 1 $ 以上 $ N $ 以下の整数 $ K $ 個からなる数列であって、要素が相異なるもののことです。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを出力せよ。

2
1 2

4

3
1 1 1

0

10
3 1 4 1 5 9 2 6 5 3

900221128

### 注記 求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P,Q $ を用いて $ \frac{P}{Q} $ と表した時、$ R\ \times\ Q\ \equiv\ P(\bmod\ 998244353) $ かつ $ 0\ \le\ R\ <\ 998244353 $ を満たす整数 $ R $ がただ一つ存在することが証明できます。この $ R $ を求めてください。 ### 制約 - $ 2\ \le\ N\ \le\ 2000 $ - $ 1\ \le\ A_i\ \le\ N $ - 入力は全て整数である。 ### Sample Explanation 1 大きさが $ 1 $ である集合を選び、かつ集合に含まれないもう一方のボールの色に変更するまで操作は続きます。その確率は $ \displaystyle\ \frac{2}{4}\ \times\ \frac{1}{2}=\frac{1}{4} $ なので、操作回数の期待値は $ 4 $ 回です。 ### Sample Explanation 2 初めから全てのボールの色が同じであるため、操作は行われません。