注意

この問題の実行時間制限は $6$ sec です。実行制限時間が厳しいため、高速な言語の使用を強く推奨します。

問題文

エトワーニュくんはバーチャル空間の黒板で勉強会をしています。かしこいですね。かわいいですね。

黒板には $N$ 個の数値が左から $A_1, A_2, \dots , A_N$ と書かれています。

エトワーニュくんは $X$ の数値を覚えながら次の操作を行います。

• 最初エトワーニュくんは $X=1$ を記憶する
• 次の操作を黒板の数値がなくなるまで繰り返す
• 黒板に書いてある好きな要素を一つ選び、この値を $Y$ とする
• 選んだ要素より左にある消されていない要素の個数を $s$ として、 $X$ を $(-1)^{s}$ 倍する
• 選んだ要素を黒板から消す
• まだ消されていない全ての要素の個数を $t$ として、 $X$ を $Y^t$ 倍する

エトワーニュくんが $A_i$ を選ぶ順番は $N!$ 通りありますが、その全てにおける $X$ の和を $998244353$ で割った余りを求めてください。

入力

$N$
$A_1\ A_2\ \dots \ A_N$

• 入力は全て整数
• $1 \le N \le 10^5$
• $0 \le A_i \le 998244352$

また、この問題には以下の制約のケースが evil ケースとして用意されている。evil ケースなので、ジャッジ結果には影響しない。

• 入力は全て整数
• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 998244352$

出力

答えを出力せよ。

サンプル

4
2 3 4 5

12

9
78 98 66 58 73 8 47 87 55

545150365

20
288 270 339 501 184 69 347 507 735 249 936 16 968 790 728 438 966 595 53 738

274218770