Problem Statement

You are given a tuple of $N$ non-negative integers $A=(A_1,A_2,\ldots,A_N)$ such that $A_1=0$ and $A_N>0$.

Takahashi has $N$ counters. Initially, the values of all counters are $0$. He will repeat the following operation until, for every $1\leq i\leq N$, the value of the $i$-th counter is at least $A_i$.

Choose one of the $N$ counters uniformly at random and set its value to $0$. (Each choice is independent of others.) Increase the values of the other counters by $1$.

Print the expected value of the number of times Takahashi repeats the operation, modulo $998244353$ (see Notes).

Note

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, one can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Constraints

• $2\leq N\leq 2\times 10^5$
• $0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}$
• $A_N>0$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the expected value of the number of times Takahashi repeats the operation, modulo $998244353$.