1839 - E.same amounts of food

問題

Yさんは友人たちとバーベキューをしようと思い、N種類の食材を買いに行った。
$i$ 番目の食材は $a_i $個セットでしか売っておらず、Yさんは全ての食材を同じ個数ずつ買わないと気が済まなかったので それぞれ $b_i$ セットずつ買うことにした。このとき、Yさんが購入した食材のセットの数の総和$S$ ($= Σ{b_i}$)の最小値を求めよ。 ただし、答えが非常に大きくなる可能性があるため、答えを998244353で割った余りを出力せよ。

入力

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

$N$
$a_1$ $a_2$ ... $a_N$

1行目に自然数$N$が与えられる。 2行目にスペース区切りで自然数$a_i (1 \leq i \leq N)$が与えられる。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N \leq 10^{5}$
• $1 \leq a_i \leq 10^{9}$

部分点

上記の制約を、

• $1 \leq N \leq 10$
• $1 \leq a_i \leq 10$
とした場合のケースで正解した場合は部分点として300点を与える。

入出力例

入力例1

3
1 2 3

出力例1

11

Yさんが3種類全ての食材を6個ずつ購入する時、食材をそれぞれ6セット、3セット、2セット買うことになり、Yさんは合計で6+3+2=11セットの食材を購入したことになる。これ以上少ないセットで全ての食材を買う方法はないため、答えは11となる。

入力例2

4
2 3 5 7

出力例2

247