問題文

黒板に N 個の非負整数 A_1,A_2,\cdots,A_N が書かれています。

AtCoder さんはこれから以下の操作を N-1 回行います。

• 黒板に書かれている数を 2 つ選び、消す。選んだ数を x,y として、新たに x \times y+1 を黒板に書き込む。

操作が完了すると、黒板には 1 つの整数が残されることになります。

黒板に書かれている数は値が同じでも互いに区別可能であるとします。 また、2 つの数を選ぶときその順序は区別しません。 つまり、操作を完了する方法は全部で \prod_{2 \leq n \leq N} n \times (n-1) /2 通りあります。

これらすべての方法について、最終的に黒板に残る数を求めたとします。 これらの値の総和を 998\,244\,353 で割ったあまりを求めてください。

制約

• 2 \leq N \leq 250\,000
• 0 \leq A_i < 998\,244\,353
• 入力はすべて整数

入力例 1

2
1 2

出力例 1

3

操作を行う方法は 1 通りだけ存在し、最後に残る数は 1 \times 2+1=3 です。

入力例 2

3
1 1 1

出力例 2

9

入力例 3

4
1 2 1 4

出力例 3

276

入力例 4

10
785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563 519729086 344065186

出力例 4

911129406