Background

Little L is a serious OCD patient.

Because of his severe OCD, whenever he draws, he always places the points on a circle.

Problem Description

One day, he asked Little H and Little W a question:

If there are $n$ distinct points on a circle, labeled from $1$ to $n$ in order, how many ways are there to connect them into a tree?

Little H & Little W: Isn’t this a dumb problem?

Little L: Then what if edges are not allowed to intersect?

Little H & Little W: Isn’t this a dumb problem?

Little L: Then what if we replace “tree” with “graph”?

Little H & Little W: Isn’t this a dumb problem?

Little L: Then what if each point has a weight $a_i$, and the weight of an edge $(i,j)$ is $a_i\times a_j$? Find the expected value of the sum of all edge weights over graphs that satisfy the conditions above.

Little H & Little W: Isn’t this a dumb problem?

After seeing that the problem he had worked on for a long time was instantly solved by a dalao, Little L felt very upset. To comfort him, you need to help solve this problem.

Notes:

1. Two edges that meet only at an endpoint are not considered intersecting.
2. A graph with no edges (i.e., only $n$ points and no edges between them) is also valid.
3. The points are numbered clockwise from $1$ to $n$.
4. The graph cannot contain self-loops or multiple edges.

Input Format

The first line contains a positive integer $n$, as described above.

The next line contains $n$ non-negative integers. The $i$-th number is $a_i$, the weight of point $i$.

Output Format

Output a positive integer representing the answer modulo $998244353$.

4
1 1 1 1

665496238

13
1 1 4 5 1 4 1 9 1 9 8 1 0

748867567

Hint

For Sample 1, all $64$ graphs are as follows:

Among them, the $48$ graphs on the left are valid, and the $16$ graphs on the right are invalid. All edge weights are $1$.

The expected sum of edge weights is $\dfrac{8}{3}$. Modulo $998244353$, the result is $665496238$.

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $10\%$ ): $n\leq 6$.
• Subtask 2 ( $30\%$ ): $n\leq 3000$.
• Subtask 3 ( $60\%$ ): no special restrictions.

For $100\%$ of the data, $2\leq n\leq 10^5,0\leq a_i\leq10^6$.

The time limit is $1s$ for Subtask 1 and Subtask 2, and $2s$ for Subtask 3.

If you do not know how to take a rational number modulo a prime, please search for “multiplicative inverse”.

Translated by ChatGPT 5