AT_dwacon5th_prelims_e Cyclic GCDs

[problemUrl]: https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_e ニワンゴくん养了 $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$ 只鸡都拉手后，可以证明它们会被分成若干个环。 一种环的组成方式的**美丽度** $f(p)$ 定义为每个环中体型最小的鸡的体型的乘积。 对于 $1 \leq i \leq N$，记 $b_i$ 为所有能将鸡分成 $i$ 个环的排列 $p$ 的 $f(p)$ 之和。 请计算 $b_1, \ldots, b_N$ 的最大公约数，并对 $998244353$ 取模输出。

输入通过标准输入给出，格式如下： ``` $N$ $a_1$ $a_2$ $\ldots$ $a_N$ ```

请输出答案。

### 限制条件 - $1 \leq N \leq 10^5$ - $1 \leq a_i \leq 10^9$ - 输入的所有数均为整数 ### 样例解释 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$。 ### 样例解释 2 即使鸡的体型相同，每只鸡也是可区分的，因此排列总是有 $N!$ 种。下图展示了 $p = (2, 1, 4, 3), p = (3, 4, 1, 2)$ 时的环的组成方式和美丽度。  由 ChatGPT 4.1 翻译