题目描述

给定正整数 $N$ 和长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。

定义 $f(l, r)$ 为 $A_l, A_{l+1}, \ldots, A_r$ 的算术平均数。

请求出

的值对 $998244353$ 取模的结果。

有理数取模的定义

在本题约束下，可以证明所求的有理数写成既约分数 $\dfrac{P}{Q}$ 时必有 $Q \not\equiv 0 \pmod{998244353}$。因此存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \le R < 998244353$，请输出这个 $R$。

输入格式

N
A_1 A_2 ... A_N

输出格式

输出答案对 $998244353$ 取模的结果。

输入示例 1

2
2 3

输出示例 1

499122184

示例 1 说明

$f(1,1) = 2$，$f(1,2) = \dfrac{2+3}{2} = \dfrac{5}{2}$，$f(2,2) = 3$。

所以总和为 $2 + \dfrac{5}{2} + 3 = \dfrac{15}{2}$。

$\dfrac{15}{2}$ 在模 $998244353$ 意义下等于 $499122184$（可以验证 $499122184 \times 2 \equiv 15$）。

输入示例 2

6
1 2 3 4 5 6

输出示例 2

499122250

示例 2 说明

$A = (1,2,3,4,5,6)$ 共有 $21$ 个区间。把每个区间的平均数加起来是一个分母含 $2, 3, 4, 5, 6$ 的分数，通分后化到模 $998244353$ 意义下就是 $499122250$。

注意分母不是单一的数，所以必须对每一种区间长度分别乘上它的逆元。

输入示例 3

9
3 1 4 1 5 9 2 6 5

输出示例 3

855638200

示例 3 说明

$N = 9$ 时区间共有 $45$ 个。答案同样是一个分母较复杂的分数在模意义下的表示。

这三组样例的答案都不是「看起来像平均数」的数，正说明模意义下的除法是乘逆元，而不是实数除法。

约束条件

• $1 \le N \le 5 \times 10^5$
• $0 \le A_i < 998244353$
• 所有输入值均为整数