マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$200$ 点

問題文

$N$ 個の正整数 $A_1, A_2, \ldots, A_N$ があります．

ここで，以下の条件を満たすような長さ $N$ の整数列 $(X_1, X_2, \ldots, X_N)$ すべてからなる集合 $S$ を考えます：

• $1 \leq X_i \leq A_i \scriptsize \; (1 \leq i \leq N)$．

$\displaystyle \sum_{X \in S} \sum X$ の値を求めてください．

• なお $\sum x$ で数列 $x$ の各項の総和を表す．

ただし，答えは非常に大きくなる場合があるので，$998244353$ で割ったあまりを出力してください．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq N$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 10^5$
• $1 \leq A_i < 2^{30} \scriptsize \; (1 \leq i \leq N)$
• 入力はすべて整数

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えを求め，$998244353$ で割ったあまりを出力せよ．

サンプル

1
2
2 3

21

$S = \{\, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3) \,\}$ ですから，答えは $(1 + 1) + (1 + 2) + (1 + 3) + (2 + 1) + (2 + 2) + (2 + 3) = 21$ です．

2
5
1 4 1 4 2
9
9 9 8 2 4 4 3 5 3 

272
26127360