Description

Bob is a very wealthy businessman, and he comes to a town with $n$ shops, numbered from $1$ to $n$. In each shop, his wealth can be multiplied by $a_i\ (a_i>1)$ when he makes a transaction there.

Unfortunately, one night, Bob gets terribly drunk and starts wandering around the streets. In other words, he will visit all $n$ shops in a random order. Although he's intoxicated and out of his mind, his subconscious will still ensure that he only visits each shop once. During his visits, he will only make a transaction in the $i$-th shop if and only if the shop's number is exactly $i$. In this case, his wealth will be multiplied by $a_i$; otherwise, his wealth will remain unchanged.

Bob, despite his intoxicated state, is also a highly temperamental person. His initial anger level is $0$. Each time he visits a shop, the shopkeeper kindly tells him how many of the previously visited shops, whose numbers are greater than the current shop's number. Bob's anger level will increase by the number of such shops.

After visiting all the shops, if Bob's anger level is odd, he will impulsively bet all his wealth. However, due to his lack of gambling skills, he will lose all of his wealth and owe the same amount he bet.

Your task is to compute the expected ratio of Bob's final wealth to his initial wealth after the entire night. You can assume that his initial wealth is any positive real number. Note that if Bob owes debt, his wealth is considered to be the negative of his debt.

Since the result might be large, output the result modulo $998244353$.

Input

The first line of input contains a positive integer $n\ (1\le n\le 10^5)$ , representing the number of shops.

The second line of input contains $n$ positive integers $a_1,a_2,\ldots,a_n\ (2\le a_i\le 10^6)$.

Output

Output a single integer representing the expected ratio of Bob's remaining wealth to his initial wealth modulo $998244353$.

Formally, let $M = 998244353$. It can be shown that the expected ratio can be expressed as an irreducible fraction $\frac{x}{y}$ such that $x$ and $y$ are integers and $y \not\equiv 0 \pmod{M}$. Output an integer $k$ in a single line such that $0 \le k < M$ and $k\cdot y \equiv x\pmod{M}$.

Samples

3
2 5 7

665496245

5
2 4 5 7 6

549034403

Note

In the first test, the possible orderings are $(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2)$, and $(3, 2, 1)$, corresponding to anger values of $0, 1, 1, 2, 2$, and $3$, respectively. The corresponding wealth ratios are $70, -2, -7, 1, 1$, and $-5$. Therefore, the expected ratio of wealth is $\frac{29}{3}$, and after taking the result modulo $998244353$, the answer is $665496245$.

Resources

电子科技大学第十五届 ACM 趣味程序设计竞赛