配点 : 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