P6694 OCD

Little L is a serious OCD patient. Because of his severe OCD, whenever he draws, he always places the points on a circle.

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**. 1. **A graph with no edges (i.e., only $n$ points and no edges between them) is also valid**. 1. The points are numbered **clockwise from $1$ to $n$**. 1. The graph **cannot contain self-loops or multiple edges**.

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 a positive integer representing the answer modulo $998244353$.

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