Problem Statement

Given is a sequence of $N$ positive integers $X = (X_1, X_2, \ldots, X_N)$.

For a positive integer $K$, let $f(K)$ be the number of triples of integers $(a,b,c)$ that satisfy all of the following conditions.

• $1\leq c \leq K$.
• $0\leq a < c$ and $0\leq b < c$.
• For each $i$, let $Y_i$ be the remainder when $aX_i + b$ is divided by $c$. Then, $Y_1 < Y_2 < \cdots < Y_N$ holds.

It can be proved that the limit $\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3}$ exists. Find this value modulo $998244353$ (see Notes).

Note

We can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, we can prove that there is a unique integer $R$ such that $R\times Q\equiv P\pmod{998244353}$ and $0\leq R < 998244353$. Find this $R$.

Constraints

• $2\leq N\leq 10^3$
• $X_i$ are positive integers such that $\sum_{i=1}^N X_i \leq 5\times 10^5$.
• $X_i\neq X_j$ if $i\neq j$.

Input

Input is given from Standard Input in the following format:

N
X_1 X_2 \ldots X_N

Output

Print $\displaystyle \lim_{K\to\infty} \frac{f(K)}{K^3}$ modulo $998244353$.