题目描述

ニワンゴくん养了 $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

输入 #1

2
4 3

输出 #1

3

输入输出样例 #2

输入 #2

4
2 5 2 5

输出 #2

2

说明/提示

限制条件

• $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 翻译