题目描述

考虑所有由以下元素组成的序列：

• $a_1$ 个数字 $1$；
• $a_2$ 个数字 $2$；
• $\ldots$
• $a_n$ 个数字 $n$。

从所有满足上述条件的序列中等概率随机选取一个。求该序列的逆序数的平方的期望，并对 $998\,244\,353$ 取模。

对于一个长度为 $L$ 的序列

其逆序数定义为满足

的有序对 $(i,j)$ 的数量。

输入格式

第一行包含一个整数 $n$，表示序列中可能出现的最大数字。

第二行包含 $n$ 个整数

其中 $a_i$ 表示数字 $i$ 出现的次数。

输出格式

输出所求期望对 $998\,244\,353$ 取模后的结果。

数据范围

样例 1

输入

2
1 1

输出

499122177

样例 2

输入

5
3 1 4 1 1

输出

166374411

说明

可以证明，逆序数平方的期望是一个有理数。设该有理数写成最简分数

则 $q$ 不会是 $998\,244\,353$ 的倍数。

定义 $\frac{p}{q}$ 对 $998\,244\,353$ 取模的结果为最小的非负整数 $x$，满足

在样例 1 中，由一个 $1$ 和一个 $2$ 组成的序列共有 12、21 两种，它们的逆序数分别为 $0$ 和 $1$。因此逆序数平方的期望为

由于

所以答案为 499122177。