配点 : $1000$ 点

問題文

ニワンゴくんは (N) 羽のニワトリを飼っています。それぞれのニワトリは (1) から (N) の番号で識別され、(i) 番目のニワトリの大きさは正の整数 (a_i) です。

(N) 羽のニワトリは手をつなぎ合っていくつかの輪を作ることにしました。 輪の作り方は (1, \ldots ,N) を並び替えた順列 (p) を用いて表され、ニワトリ (i) が右手 (ないし右翼) でニワトリ (p_i) の左手を取ることを表します。ニワトリは自分自身の手を取ることもあります。

ニワトリ (i) を含む 輪 を、ニワトリ (p_i, p_{p_i}, \ldots, p_{\ddots_i} = i) からなる集合とします。 こうして (N) 羽全てのニワトリが手を取ったとき、(N) 羽のニワトリたちは何個かの輪に分割できることが証明できます。

輪の作り方の 美しさ (f(p)) はそれぞれの輪に含まれる最も小さいニワトリの大きさの積で定義されます。

(1 \leq i \leq N) を満たす (i) について、上の方法で輪が (i) 個できるような順列 (p) について (f(p)) を足し合わせたものを (b_i) とします。

(b_1, \ldots, b_N) の最大公約数を、modulo (998244353) で求めてください。

制約

• (1 \leq N \leq 10^5)
• (1 \leq a_i \leq 10^9)
• 入力で与えられる数値は全て整数である

入力

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

(N)

(a_1) (a_2) (\ldots) (a_N)

出力

答えを出力せよ。

入力例1

2
4 3

出力例1

3

(N = 2, a = [ 4, 3 ]) である。

順列 (p = [ 1, 2 ]) について、ニワトリ (1) のみからなる輪とニワトリ (2) のみからなる輪ができるので、(f([1, 2]) = a_1 \times a_2 = 12) である。

順列 (p = [ 2, 1 ]) について、ニワトリ (1, 2) からなる輪ができ、その輪の最も小さいニワトリの大きさは (a_2 = 3) なので、(f([2, 1]) = a_2 = 3) である。

以上から (b_1 = f([2, 1]) = 3, b_2 = f([1, 2]) = 12) なので、(b_1) と (b_2) の最大公約数は (3) である。

入力例2

4
2 5 2 5

出力例2

2

ニワトリは大きさが同じであっても互いに区別できるため、常に (N!) 通りの順列が存在する。

以下の図は (p = (2, 1, 4, 3), p = (3, 4, 1, 2)) の場合の輪の作り方および美しさである。