题目描述

ニワンゴくんは \(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\) で求めてください。

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

【题目描述】

给定一个长为 $N$ 的序列 $a_1,a_2,\dots,a_N$。

设一个置换 $p$ 的价值 $f(p)$ 为每个轮换中最小的 $a_i$ 的乘积。

设 $b_i$ 为有 $i$ 个轮换的所有置换 $p$ 的 $f(p)$ 之和。

求 $\gcd(b_1,b_2,\dots,b_N) \bmod{998244353}$。

【数据范围】

$1\le N\le10^5$，$1\le a_i\le10^9$。

2
4 3

3

4
2 5 2 5

2

提示

制約

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

Sample Explanation 1

\\(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\\) である。

Sample Explanation 2

ニワトリは大きさが同じであっても互いに区別できるため、常に \\(N!\\) 通りの順列が存在する。 以下の図は \\(p = (2, 1, 4, 3), p = (3, 4, 1, 2)\\) の場合の輪の作り方および美しさである。