21270번 - 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.

제한

힌트