Problem Background

In the year 4202, Xiao K, a gaLaxy enGineer Master who has been working for 3143 days, established a base on the OIPA115 planet in the XS41 galaxy to assist humanity in exploring the unknown. Here, he set up several energy fields. Initially, he decided to use pawns to transport energy, but after two of his controlled red pawns collided and lost all their energy, he decided to connect them with energy pipelines instead, and make the energy pipelines at an angle of $(180+\mathrm{eps})^\circ$.

Problem Description

Xiao K has $n$ energy fields, with the $i$-th energy field storing $a_i$ units of energy.

Xiao K has established $n$ different bidirectional energy pipelines between the energy fields, ensuring that every pair of energy fields is connected.

For a pipeline, its energy level is the sum of the energies of the two energy fields it connects.

Xiao K's satisfaction with a set of $n$ different energy pipelines is the product of the energy levels of all the pipelines.

Now, Xiao K wants to know the total satisfaction for all different valid ways of constructing the energy pipelines. Since Xiao K's satisfaction is an integer within $[0, 998244353)$, you only need to output the total satisfaction modulo $998244353$.

Two ways of constructing pipelines are considered different if and only if there exists at least one pipeline connecting energy fields $i$ and $j$ that appears in one construction but not the other.

Formal Problem Statement

Given a complete graph $G(V, E)$ with $n$ vertices. Each vertex has a weight $a_i$. The edge weight between vertices $i$ and $j$ is $w_{i,j} = a_i + a_j$.

Define the weight of a connected subgraph $G'(V, E')$ such that $E' \in E$ as $\prod_{e \in E'} w_e$. Note that the subgraph's vertex set is the full set.

Find the sum of the weights of all fundamental cycle trees in $G(V, E)$, modulo $998244353$.

The fundamental cycle trees must have no duplicate edges or self-loops.

Input Format

The first line contains a positive integer $n$, representing the number of energy fields.

The second line contains $n$ non-negative integers $a_i$, representing the energy stored in the $i$-th energy field.

Output Format

A single line containing a non-negative integer, representing the total satisfaction for all different ways of constructing energy pipelines, modulo $998244353$.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

60

Sample Input #2

4
1 2 3 4

Sample Output #2

8629

Sample Input #3

7
1 9 1 9 8 1 0

Sample Output #3

311816897

Sample Input #4

16
2 0 0 9 0 2 2 8 2 0 0 9 0 8 1 5

Sample Output #4

871736512

Notes

Sample Explanation 1

The only possible fundamental cycle tree shape is a cycle with three points, where the edges $(1,2)$, $(1,3)$, and $(2,3)$ have weights $3, 4, 5$ respectively, and their product is $60$.

Data Range and Constraints

This problem uses bundled testing.

Special Conditions: Guarantees $\forall i \in [1, n], a_i = 499122177$.

For all data, guarantees $3 \leq n \leq 1000$, $0 \leq a_i < 998244353$.

见题面 Input 部分

见题面 Output 部分