分数: 625 点
问题陈述
有 N 车牌编号 1 通过 N。 菜品 i 有 a_i 上面有石头。 还有一个空袋子。
您可以按任意顺序执行任意次数(可能为零)以下两种操作。
- 从每个带有一颗或多颗石子的盘子中取出一颗石子。 将取出的石头放入袋子中。
- 采取 N 从袋子里拿出石头,然后在每个盘子里放一颗石头。 只有当袋子有时才能执行此操作 N 或更多石头。
让 b_i 是板上石子的数量 i 完成操作后。 打印数字,模数 998244353,整数序列 (b_1, b_2, \dots, b_N) 长度 N 可能由操作产生。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq a_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \dots a_N
输出
打印数字,模数 998244353,可能的序列 (b_1, b_2, \dots, b_N).
示例输入 1
3 3 1 3
示例输出 1
7
例如, b 变为 (2, 1, 2) 通过以下过程。
- 执行第一个操作。 b 变为 (2, 0, 2).
- 执行第一个操作。 b 变为 (1, 0, 1).
- 执行第二个操作。 b 变为 (2, 1, 2).
以下七个序列可以是结果 b.
- (0, 0, 0)
- (1, 0, 1)
- (1, 1, 1)
- (2, 0, 2)
- (2, 1, 2)
- (2, 2, 2)
- (3, 1, 3)
示例输入 2
1 0
示例输出 2
1
有一个序列, (0),这可能是结果 b.
示例输入 3
5 1 3 5 7 9
示例输出 3
36
示例输入 4
10 766294629 440423913 59187619 725560240 585990756 965580535 623321125 550925213 122410708 549392044
示例输出 4
666174028