問題文

無限に伸びる数直線と、変数 ii があります。さらに、 N+1N+1 個の整数 A0,A1,,ANA_0, A_1, \cdots, A_N が与えられます。

数直線の原点 OO は座標 00 を指すこととします。最初、しょぼん君は数直線の原点 OO におり、変数 ii00 に初期化されています。しょぼん君は次の操作をちょうど NN 回繰り返します。

  • 1,+1-1, +1 のいずれかを等確率に選び、それを dd とする。しょぼん君の座標を kk として、しょぼん君は座標 k+dk+d に移動する。その後、もししょぼん君が数直線の原点 OO にいたら、 ii11 を足す。

しょぼん君のスコアは AiA_i になります。ここで、いかなる場合でも 0iN0 \le i \le N であることが証明できます。

しょぼん君が得られるスコアの期待値を modulo 998244353998244353 で求めてください。

modulo 998244353998244353 で求めることについて

スコアの期待値は有理数であることが証明されます。さらに、この問題の制約下では、答えを既約分数 y/xy/x で表したとき、 xx998244353998244353 で割り切れないことが証明されます。このとき、 00 以上 998244353998244353 未満の唯一の整数 zz が存在して、 xzy(mod998244353)xz \equiv y \pmod{998244353} となります。この zz を出力してください。

制約

  • 1N1051 \le N \le 10^5
  • 0Ai<9982443530 \le A_i < 998244353 (0iN0 \le i \le N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

NN\\ A0A_0 A1A_1 A2A_2 \cdots ANA_N

出力

答えを出力せよ。

サンプル1

入力
4
3 1 4 1 5
出力
499122179

サンプルの入力では、しょぼん君は 3/83/8 の確率でスコア 333/83/8 の確率でスコア 111/41/4 の確率でスコア 44 を得ます。

よって、期待値は 3×38+1×38+4×14=523 \times \frac{3}{8} + 1 \times \frac{3}{8} + 4 \times \frac{1}{4} = \frac{5}{2} です。 modulo 998244353998244353 においては、この値は 499122179499122179 になります。

提出


Go (1.21)