题目描述

有编号为 $1, 2, \ldots, N$ 的 $N$ 个人围成一个环形排列。

对于每个满足 $1 \leq i \leq N-1$ 的人 $i$，其右边是人 $i+1$，而人 $N$ 的右边是人 $1$。

每个人 $i$ 最初拥有 $a_i$ 个球。

接下来进行如下操作一次：

• 每个人可以从自己当前拥有的球中选出若干个（可以为 $0$ 个）。
• 然后，每个人将自己选中的球同时传递给右边的人。
• 形成一个长度为 $N$ 的数列。数列的第 $i$ 项等于人 $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)\}$。

请计算 $\sum_{x \in S} \prod_{i=1}^{N} x_i$，并输出其对 $998244353$ 取模的结果。

输入格式

输入为一行，包含 $N$ 和 $a_1, a_2, \ldots, a_N$，用空格分隔。

输出格式

输出 $\sum_{x \in S} \prod_{i=1}^{N} x_i$ 对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

3
1 1 1

输出 #1

1

输入输出样例 #2

输入 #2

3
2 1 1

输出 #2

6

输入输出样例 #3

输入 #3

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

输出 #3

864609205

说明/提示

限制

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

样例解释 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$。

样例解释 3

• 不要忘记对 $998244353$ 取模。