問題文

$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$ 個からなる数列であって、要素が相異なるもののことです。

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $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$
• 入力は全て整数である。

入力

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

$N$ $A_1$ $A_2$ $\\dots$ $A_N$

出力

答えを出力せよ。

入力例 1

2
1 2

出力例 1

4

大きさが $1$ である集合を選び、かつ集合に含まれないもう一方のボールの色に変更するまで操作は続きます。その確率は $\\displaystyle \\frac{2}{4} \\times \\frac{1}{2}=\\frac{1}{4}$ なので、操作回数の期待値は $4$ 回です。

入力例 2

3
1 1 1

出力例 2

0

初めから全てのボールの色が同じであるため、操作は行われません。

入力例 3

10
3 1 4 1 5 9 2 6 5 3

出力例 3

900221128