← 返回题目列表

AtCoder · arc124_e

E. 传递到下一个

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

N 称为 Person 的人 1, 2, \ldots, N 站成一圈。

对于每个 1 \leq i \leq N-1, 人 i右边的邻居是 Person i+1和人 N右边的邻居是 Person 1.

人 i 最初有 a_i 球。

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

  • 每个人选择他们拥有的一些球(可能是零)。
  • 然后,每个人 同时 将选定的球交给右边的邻居。
  • 现在,制作一个长度为 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.

约束

  • 输入中的所有值都是整数。
  • 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 is 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.