Background

In the year 4202, Little K, a gaLaxy enGineer Master who has been working for 3143 days, built an outpost on planet OIPA115 in the XS41 galaxy to help humans explore the unknown. There, he set up some energy fields. He originally planned to use some pawns (zu, 卒) to transport energy, but after two red pawns under his control collided and lost all their energy, he decided that he should instead connect them with energy pipelines, and make the energy pipelines form a $(180+\mathrm{eps})^\circ$ angle.

Problem Description

Little K has $n$ energy fields. The $i$-th energy field stores $a_i$ units of energy.

Little K builds $n$ distinct undirected energy pipelines between the energy fields, so that all energy fields are connected to each other (i.e., the resulting graph is connected).

For an energy pipeline, its energy level is the sum of the energies of the two energy fields at its ends.

Little K’s satisfaction for a set of $n$ distinct energy pipelines is the product of the energy levels of all pipelines.

Now Little K wants to know: among all different valid ways to build the energy pipelines, what is the total sum of satisfaction values? Since Little K’s satisfaction is an integer in $[0,998244353)$, you only need to output the total satisfaction modulo $998244353$.

Two ways of building pipelines are different if and only if there exists at least one pipeline connecting energy fields $i,j$ that appears in exactly one of the two ways.

[Formal Statement]

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

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

Compute the sum of the weights of all unicyclic graphs (connected graphs with exactly one cycle) among the connected subgraphs of $G(V,E)$, modulo $998244353$.

A unicyclic graph must have no multiple edges and no self-loops.

Input Format

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

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

Output Format

One line containing a non-negative integer, denoting the total sum of satisfaction values over all different ways to build the energy pipelines, modulo $998244353$.

3
1 2 3

60

4
1 2 3 4

8629

7
1 9 1 9 8 1 0

311816897

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

871736512

Hint

Sample Explanation 1

The only possible unicyclic form is a 3-vertex cycle. The edge weights of cycle edges $(1,2),(1,3),(2,3)$ are $3,4,5$ respectively, and their product is $60$.

Constraints

This problem uses bundled testdata.

Special property: it is guaranteed that $\forall i\in[1,n],a_i=499122177$.

For all testdata, it is guaranteed that $3\leq n\leq 1000$ and $0\leq a_i<998244353$.

Translated by ChatGPT 5