408068: GYM102978 F Find the LCA

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$$$.

The 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$$$).

Print the answer.

3
2 2 2

12

5
1 2 3 4 5

2080