問題文

AliceとBobが石取りゲームをすることを考えます。最初、山がいくつかあり、それぞれの山には $1$ 個以上の石があります。

ゲーム開始時に、チーターのBobは山を一つ選択しその山の石を全て取り除くことができます。この行動を行うかどうかは、Bobが任意に選択可能です。

その後、Aliceから始めて $2$ 人は交互に以下の操作を繰り返します。

• 石が $1$ つ以上残っているような山を $1$ つ選ぶ。選んだ山に $X$ 個の石があるとき、 $1$ 個以上 $X$ 個以下の任意の個数の石をその山から取り除く。

先に操作ができなくなったプレイヤーが負けとなります。

さて、ゲームを始める前の初期状態を、以下の方法で生成します。

• はじめ石の置かれた山は存在しない。
• 以下のステップを行う。

1. 整数 $i\in\left\{0,1,2,\dots,N\right\}$ をランダムに選ぶ。ただし $i$ が選ばれる確率は $\displaystyle\frac{A_i}{\sum_{i=0}^NA_i}$ であり、ステップごとの試行は独立である。
2. もし $i$ が正の数だった場合、$i$ 個石が置かれた山を新たに追加し、ステップ $1$ に戻る。そうでないとき現在の状態を初期状態とし、ステップを終了する。

AliceもBobも自分が勝つために最適な行動をするとき、Aliceの勝率を求めてください。ただしAliceの勝率は有理数で表せることが証明可能なので、 $\bmod998244353$ で出力してください。

制約

入力

$N\ $
$A_0$ $A_1$ $\dots$ $A_N$

出力

最後に改行してください。

サンプル

2
1 1 1

732045859

5
27182 81828 45904 52353 60287 47135

450579757