A - Random Descents Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の正整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． 以降，S=\sum_{1 \leq i \leq N} A_i とおきます．

長さ S の整数列 x は以下の条件をすべて満たすとき（そしてそのときのみ）good であると言います．

  • 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} を満たす index i の個数を f(x) と表すことにします．

good な整数列 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

good な 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