题目描述

有 $N$ 个编号为 $1$ 到 $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$ 取模后的结果。

注意：我们可以证明所求期望值总是一个有理数。在此问题的约束下，当该值被两个互质的整数 $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