問題文

$1, 2, \\ldots, N$ の番号がついた人が円環状に並んでいます。

$1 \\leq i \\leq N-1$ を満たす人 $i$ の右隣に人 $i+1$ がおり、人 $N$ の右隣には人 $1$ がいます。

人 $i$ ははじめ、$a_i$ 個のボールを持っています。

以下の処理を一度だけ行います。

• それぞれの人が現在持っているボールのうちいくつかを選ぶ($0$ 個でもよい)
• その後、選んだボールを全て右隣の人に 同時に 渡す。
• 長さ $N$ の数列を作る。数列の $i$ 番目の要素は人 $i$ が現在持っているボールの個数と等しい値である。

処理の結果できる数列としてありうるものの集合を $S$ とします。 たとえば、$a=(1,1,1)$ のとき $S= \\{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \\}$ です。

$\\sum_{x \\in S} \\prod_{i=1}^{N} x_i$ を $998244353$ で割ったあまりを計算してください。

制約

• 与えられる入力は全て整数
• $3 \\leq N \\leq 10^5$
• $0 \\leq a_i \\leq 10^9$

入力

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

$N$ $a_{1}$ $a_{2}$ $\\cdots$ $a_{N}$

出力

$\\sum_{x \\in S} \\prod_{i=1}^{N} x_i$ を $998244353$ で割ったあまりを出力せよ。

入力例 1

3
1 1 1

出力例 1

1

• $S= \\{(0,1,2),(0,2,1),(1,0,2),(1,1,1),(1,2,0),(2,0,1),(2,1,0) \\}$ です。
• $\\sum_{x \\in S} \\prod_{i=1}^{N} x_i$ は $1$ です。

入力例 2

3
2 1 1

出力例 2

6

入力例 3

20
5644 493 8410 8455 7843 9140 3812 2801 3725 6361 2307 1522 1177 844 654 6489 3875 3920 7832 5768

出力例 3

864609205

• $998244353$ で割ったあまりを求めるのを忘れずに。