染色

题目描述

有 $N$ 个球,编号为 $1$ 到 $N$。最初,球 $i$ 涂有颜色 $A_i$。

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

重复以下操作,直到所有球的颜色相同:

• 在由 $N$ 个球组成的集合的 $2^N$ 个子集(包括空集)中等概率选择一个。设选中的球的编号为 $X_1, X_2, \dots, 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$ 之间两两不同的 $K$ 个整数组成的序列。

输入格式

输入按以下格式从标准输入给出:

N
A_1 A_2 … A_N

输出格式

输出答案。

样例

2
1 2

4

操作会一直重复,直到选中大小为 $1$ 的子集,并将该球的颜色改为子集中未包含的球的颜色。该事件的概率为 $\displaystyle \frac{2}{4} \times \frac{1}{2}=\frac{1}{4}$,因此期望值为 $4$。

3
1 1 1

0

由于所有球的颜色已经相同,一次操作都不会进行。

10
3 1 4 1 5 9 2 6 5 3

900221128

数据范围

• $2 \le N \le 2000$
• $1 \le A_i \le N$
• 输入中的所有值都是整数。

提示

可以证明所求期望值总是有理数。此外,在本题的约束下,当用两个互素的整数 $P$ 和 $Q$ 将该值表示为 $\frac{P}{Q}$ 时,可以证明存在唯一的整数 $R$,满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \le R \lt 998244353$。输出这个 $R$。