102497: [AtCoder]ABC249 Ex - Dye Color

Problem Statement

There are $N$ balls numbered $1$ through $N$. Initially, Ball $i$ is painted in Color $A_i$.

Colors are represented by integers between $1$ and $N$, inclusive.

Consider repeating the following operation until all the colors of the balls become the same.

• There are $2^N$ subsets (including the empty set) of the set consisting of the $N$ balls; choose one of the subsets uniformly at random. Let $X_1,X_2,...,X_K$ be the indices of the chosen balls. Next, choose a permutation obtained by choosing $K$ integers out of integers $(1,2,\dots,N)$ uniformly at random. Let $P=(P_1,P_2,\dots,P_K)$ be the chosen permutation. For each integer $i$ such that $1 \le i \le K$, change the color of Ball $X_i$ to $P_i$.

Find the expected value of number of operations, modulo $998244353$.

Here a permutation obtained by choosing $K$ integers out of integers $(1,2,\dots,N)$ is a sequence of $K$ integers between $1$ and $N$, inclusive, whose elements are pairwise distinct.

Notes

We can prove that the sought expected value is always a rational number. Also, under the Constraints of this problem, when the value is represented by two coprime integers $P$ and $Q$ as $\frac{P}{Q}$, we can prove that there exists a unique integer $R$ such that $R \times Q \equiv P(\bmod\ 998244353)$ and $0 \le R < 998244353$. Find this $R$.

Constraints

• $2 \le N \le 2000$
• $1 \le A_i \le N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

2
1 2

Sample Output 1

4

The operation is repeated until a subset of size $1$ is chosen and the color of the ball is changed to the color of the ball not contained in the subset. The probability is $\displaystyle \frac{2}{4} \times \frac{1}{2}=\frac{1}{4}$, so the expected value is $4$.

Sample Input 2

3
1 1 1

Sample Output 2

0

The operation is never performed, since the colors of the balls are already the same.

Sample Input 3

10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

900221128

问题描述

有编号为$1$到$N$的$N$个球。最初，第$i$个球涂成颜色$A_i$。

颜色用$1$到$N$之间的整数表示。

考虑重复以下操作，直到所有球的颜色都变为相同的颜色。

• 在由$N$个球组成的集合中有$2^N$个子集（包括空集）；随机选择其中一个子集。设$X_1,X_2,...,X_K$为选择的球的索引。接下来，随机选择一个从$(1,2,\dots,N)$中选择$K$个整数得到的排列。设$P=(P_1,P_2,\dots,P_K)$为选择的排列。对于满足$1 \le i \le K$的整数$i$，将第$X_i$个球的颜色更改为$P_i$。

求操作次数的期望值，对$998244353$取模。

通过从$(1,2,\dots,N)$中选择$K$个整数得到的排列是一个包含$1$到$N$之间的整数，且元素两两不同的序列。

注意

我们可以证明所求期望值总是有理数。此外，在本问题的约束下，当该值表示为两个互素的整数$P$和$Q$的比值$\frac{P}{Q}$时，我们可以证明存在唯一的整数$R$，使得$R \times Q \equiv P(\bmod\ 998244353)$且$0 \le R < 998244353$。求这个$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