I - Back to Origin

問題文

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

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

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

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

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

modulo $998244353$ で求めることについて

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

制約

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

入力

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

出力

答えを出力せよ。

サンプル1

4
3 1 4 1 5

499122179

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

よって、期待値は $3 \times \frac{3}{8} + 1 \times \frac{3}{8} + 4 \times \frac{1}{4} = \frac{5}{2}$ です。 modulo $998244353$ においては、この値は $499122179$ になります。