← 返回题目列表

AtCoder · ajo2024_final_f

F. 融合2

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

配点 : 1300 点

問題文

在黑板上 N 非负整数 A_1,A_2,\cdots,A_N 已经写好了。

AtCoder 现在将执行以下操作: N-1 将进行。

  • 从黑板上选择 2 个数字并擦掉。选出的数字作为 x,y ,并在黑板上写入新的 x \times y+1 。

操作完成后,黑板上将剩下 1 个整数。

假设黑板上书写的数字即使值相同,也可以相互区分。此外,选择2 个数字时,不区分顺序。也就是说,完成操作的方法共有 \prod_{2 \leq n \leq N} n \times (n-1) /2 种。

对于所有这些方法,假设要求最终黑板上剩下的数字。将这些值的总和除以 998\,244\,353 的余数。

制約

  • 2 \leq N \leq 250\,000
  • 0 \leq A_i < 998\,244\,353
  • 输入全为整数。

入力

输入如下格式从标准输入给出。

N
A_1 A_2 \cdots A_N

出力

请输出答案。


入力例 1

2
1 2

出力例 1

3

进行操作的方法只有 1 种,最后剩下的数是 1 \times 2+1=3 。


入力例 2

3
1 1 1

出力例 2

9

入力例 3

4
1 2 1 4

出力例 3

276

入力例 4

10
785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563 519729086 344065186

出力例 4

911129406