配点 : 300 点
問題文
长度 N 的正整数序列 给出了 A=(A_1,A_2,\cdots,A_N) 。 从此, 比方说S=\sum_{1 \leq i \leq N} A_i 。
长度 S 整数序列 x 当(且仅当)满足以下所有条件时: 我们说好 。
- x 的每个元素是 1 以上 N 以下
- 各整数 i (1 \leq i \leq N), 满足x 只是 A_i 的 包含 i 对于
整数列 x=(x_1,x_2,\cdots,x_S) , 满足x_i>x_{i+1} 的索引 i 的数量 我们将其表示为 f(x) 。
好的整数序列 当 x 随机均匀取时, f(x) 的预期值为 使用 \pmod{998244353} 找到它。
期待値 \pmod{998244353} 的定义
可以证明期望的期望值始终是有理数。另外,在这个问题的约束下,我们可以将该值转换为不可约分数 当表示为 \frac{P}{Q} 时, 也可以证明Q \neq 0 \pmod{998244353} 。因此, 满足R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 的整数 R 是唯一确定的。这个 请回答 R 。
制約
- 2 \leq N \leq 250000
- 1 \leq A_i
- \sum_{1 \leq i \leq N} A_i < 998244353
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \cdots A_N
出力
打印答案。
入力例 1
2 1 2
出力例 1
665496236
好 x 如下 3 没错。
- x=(1,2,2): f(x)=0
- x=(2,1,2): f(x)=1
- x=(2,2,1): f(x)=1
因此 其被确定为 f(x) 的期望值为 2/3 。 对于
入力例 2
5 1 1 1 1 1
出力例 2
2
入力例 3
2 2024 824
出力例 3
841217737
入力例 4
10 19237224 3435339 227368010 836006 153314679 115537801 189694444 76016030 159566203 53238564
出力例 4
873203747