ストーリー

必ずしもこの項を読む必要はない．

何らかの大会のチーム分けの場面を考えましょう．

チームの強さを単純にそのチームに属する人の強さの合計とします．すると，チーム数が同じであれば全チームの強さの総積が大きいほど偏りが少ないと考えることができます．

そのような計算をすべてのチーム分けに対して行うことを考えてみましょう．

問題文

長さ $N$ の数列 $A$ が与えられます． 以下を満たす正整数の集合の集合 $S$ を「良いグループの分け方」と呼ぶことにします．

• 任意の $S$ の要素 $T$ について， $\lvert T \rvert \geq 1$
• $\displaystyle\sum_{T \in S} \lvert T \rvert = N$
• 任意の $S$ の相異なる要素 $T,U$ について， $T \cap U=\varnothing$
• すべての $1$ 以上 $N$ 以下の整数 $i$ について，ある $T \in S$ が存在して， $i \in T$

このとき，良いグループの分け方 $S$ すべてについて以下の値を求め，その値の総和を求めてください．ただし答えは非常に大きくなりうるので $998244353$ で割った余りを出力してください．

• $\displaystyle\prod_{T \in S} \displaystyle\sum_{i \in T} A_{i}$

制約

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq A_{i} \leq 10^{18}$
• 入力はすべて整数

入力

$N$
$A_{1}~~~A_{2} ~~\ldots ~~A_{N}$

出力

答えを出力せよ．

サンプル

3
1 2 3

34

1
1

1

5
1 1 1 1 1

196