408068: GYM102978 F Find the LCA
Description
You are given an integer sequence $$$A_1,A_2,\ldots,A_N$$$. You'll make a rooted tree with $$$N$$$ vertices numbered from $$$1$$$ through $$$N$$$. The vertex $$$1$$$ is the root, and for each vertex $$$i$$$ ($$$2 \leq i \leq N$$$), its parent $$$p_i$$$ must satisfy $$$p_i<i$$$.
You define the score of a rooted tree as follows:
- Let $$$x$$$ be the lowest common ancestor of the vertex $$$N-1$$$ and the vertex $$$N$$$. Then, the score is
$$$$$$ \prod_{v \in (\text{subtree rooted at $x$})} A_v $$$$$$
Note that we consider $$$x$$$ itself is in the subtree rooted at $$$x$$$.
There are $$$(N-1)!$$$ ways to make a tree. Find the sum of scores of all possible trees, modulo $$$998244353$$$.
InputThe first line contains an integer $$$N$$$ ($$$3 \leq N \leq 250000$$$).
The second line contains integers $$$A_1,A_2,\ldots,A_N$$$ ($$$1 \leq A_i < 998244353$$$).
OutputPrint the answer.
ExamplesInput3 2 2 2Output
12Input
5 1 2 3 4 5Output
2080