题目描述

给定一个正整数序列 $X = (X_1, X_2, \ldots, X_N)$。

对于一个正整数 $K$，令 $f(K)$ 表示满足以下条件的整数三元组 $(a,b,c)$ 的数量：

• $1\leq c \leq K$。
• $0\leq a < c$ 且 $0\leq b < c$。
• 对于每个 $i$，令 $Y_i$ 表示将 $aX_i + b$ 除以 $c$ 所得到的余数。那么满足 $Y_1 < Y_2 < \cdots < Y_N$。

可以证明极限 $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3}$ 存在。找到这个极限值对 $998244353$ 取模（参见注释）。

注释

我们可以证明所讨论的极限始终是一个有理数。此外，在问题的约束条件下，当将该数表示为 $\\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数时，我们可以证明存在唯一的整数 $R$，满足 $R\\times Q\\equiv P\\pmod{998244353}$ 且 $0\\leq R < 998244353$。找到这个 $R$。

约束条件

• $2\leq N\leq 10^3$
• $X_i$ 是正整数，且满足 $\\sum_{i=1}^N X_i \leq 5\times 10^5$。
• 如果 $i\neq j$，则 $X_i\neq X_j$。

输入

输入以以下格式从标准输入给出：

$N$ $X_1$ $X_2$ $\ldots$ $X_N$

输出

输出 $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3}$ 对 $998244353$ 取模。

示例输入 1

3
3 1 2

示例输出 1

291154603

例如，当 $(a,b,c) = (3,5,7)$ 时，我们有 $Y_1 = 0$，$Y_2 = 1$，$Y_3 = 4$，满足 $Y_1 < Y_2 < Y_3$。

我们有 $f(1) = 0$，$f(2) = 0$，$f(3) = 1$，$f(4) = 2$，$f(5) = 5$。

我们有 $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = \\frac{1}{24}$。

示例输入 2

3
5 9 2

示例输出 2

832860616

我们有 $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = \\frac{55}{1008}$。

示例输入 3

2
2 3

示例输出 3

166374059

我们有 $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = \\frac{1}{6}$。

示例输入 4

4
4 5 3 2

示例输出 4

0

我们有 $\\displaystyle \\lim_{K\\to\\infty} \\frac{f(K)}{K^3} = 0$。