题目描述

有 $N$ 个人，分别称为 Person $1, 2, \ldots, N$，站在一个圆圈里。

对于每个 $1 \leq i \leq N-1$，Person $i$ 右边的邻居是 Person $i+1$，Person $N$ 的右边邻居是 Person $1$。

开始时，Person $i$ 有 $a_i$ 个球。

他们只会执行以下过程一次：

• 每个人选择他们拥有的一些（可能为零）球。
• 接着，每个人同时将选定的球传递给右边的邻居。
• 现在，构造一个长度为 $N$ 的序列，其中第 $i$ 项是 Person $i$ 当前拥有的球的数量。

令 $S$ 为可以由该过程产生的所有序列的集合。例如，当 $a=(1,1,1)$ 时，我们有 $S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0)\}$。

计算对于所有 $x \in S$，$\\sum_{i=1}^{N} x_i$ 的乘积，对 $998244353$ 取模。

约束条件

• 输入中的所有值均为整数。
• $3 \leq N \leq 10^5$
• $0 \leq a_i \leq 10^9$

输入

输入以以下格式从标准输入中给出：

$N$

$a_{1}$ $a_{2}$ $\cdots$ $a_{N}$

输出

打印 $\\sum_{x \in S} \prod_{i=1}^{N} x_i$，对 $998244353$ 取模。

示例输入 1

3
1 1 1

示例输出 1

1

• 我们有 $S= \{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0)\}$。
• $\\sum_{x \in S} \prod_{i=1}^{N} x_i$ 等于 $1$。

示例输入 2

3
2 1 1

示例输出 2

6

示例输入 3

20
5644 493 8410 8455 7843 9140 3812 2801 3725 6361 2307 1522 1177 844 654 6489 3875 3920 7832 5768

示例输出 3

864609205

• 计算结果需要对 $998244353$ 取模。