给定一个整数序列 $A_1, A_2, \dots, A_N$。你需要构建一棵有 $N$ 个顶点的有根树，顶点编号从 $1$ 到 $N$。顶点 $1$ 是根节点，对于每个顶点 $i$ ($2 \le i \le N$)，其父节点 $p_i$ 必须满足 $p_i < i$。

你定义一棵有根树的得分为：

• 令 $x$ 为顶点 $N-1$ 和顶点 $N$ 的最近公共祖先。则得分为 $$\prod_{v \in (\text{以 } x \text{ 为根的子树})} A_v$$

注意，我们认为 $x$ 本身也在以 $x$ 为根的子树中。

共有 $(N-1)!$ 种构建树的方法。求所有可能树的得分之和，对 $998244353$ 取模。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 250000$)。 第二行包含整数 $A_1, A_2, \dots, A_N$ ($1 \le A_i < 998244353$)。

输出格式

输出答案。

样例

输入 1

3
2 2 2

输出 1

12

输入 2

5
1 2 3 4 5

输出 2

2080