你有一个包,里面装着 $$$n$$$ 卡。每张卡上都写有一个号码;第 $$$i$$$ 卡上的号码是 $$$a_i$$$。
您正在玩以下游戏。在每个回合中,您选择并从袋子中随机取出一张卡片(仍然留在袋子内的所有卡片都会被同等地选择)。在第一回合中没有发生任何其他事情 - 但在接下来的回合中,在移除一张卡后(令其上的数字为 $$$x$$$),您将其与上一回合中移除的卡进行比较(令其上的数字为 $$$y$$$)。可能的结果是:
- 如果 $$$x < y$$$,游戏结束,你输;
- 如果 $$$x = y$$$,游戏结束,你获胜;
- 如果 $$$x > y$$$,游戏继续。
如果袋子里没有牌了,你就输了。取出卡片后,卡片不会放回包中。
你必须计算在这场游戏中获胜的概率。可以证明其形式为$$$\frac{P}{Q}$$$,其中$$$P$$$和$$$Q$$$为非负整数,$$$Q \neq 0$$$, $$$P \le Q$$$。输出 $$$P \cdot Q^{−1} ~(mod ~~ 998244353)$$$ 的值。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5000$$$) — 袋子中的卡片数量。
第二个 live 包含 $$$n$$$ 整数 $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le n$$$) — 第 $$$i$$$ 个整数是写在第 $$$i$$$ 卡上的数字。
输出
打印一个整数 — 在这场游戏中获胜的概率以 $$$998244353$$$ 为模。
示例
输入 #1
5 1 1 4 2 3
输出 #1
299473306
输入 #2
2 2 2
输出 #2
1
输入 #3
5 4 5 1 3 2
输出 #3
0
输入#4
4 1 3 4 3
输出#4
748683265
注意
在第一个测试用例中,获胜的概率为 $$$\frac{1}{10}$$$。
在第二个测试用例中,获胜的概率为 $$$1$$$。
在第三个测试用例中,获胜的概率为 $$$0$$$。
在第四个测试用例中,获胜的概率为 $$$\frac{1}{4}$$$。