MathJax.Hub.Config({ tex2jax: {skipTags:["script","noscript","style","textarea","code"],inlineMath: [['\\(','\\)']]} });

### 问题描述

Niwango-kun有 \\(N\\) 只鸡作为宠物。鸡被编号为 \\(1\\) 至 \\(N\\)，第 \\(i\\) 只鸡的大小是正整数 \\(a\_i\\)。

\\(N\\) 只鸡决定互相牵手（翅膀），并形成一些循环。通过排列 \\(p\\) 来表示循环的方式，排列由 \\(1, \\ldots , N\\) 组成。第 \\(i\\) 只鸡用右手握住鸡 \\(p\_i\\) 的左手。鸡可以握住自己的手。

定义包含鸡 \\(i\\) 的 _循环_ 为由鸡 \\(p\_i, p\_{p\_i}, \\ldots, p\_{\\ddots\_i} = i\\) 组成的集合。可以证明，在每只鸡互相握住一些鸡的手之后，这 \\(N\\) 只鸡可以被分解成一些循环。

形成循环的方式的 _美丽度_ \\(f(p)\\) 定义为每个循环中最小鸡的大小的乘积。令 \\(b\_i \\ (1 \\leq i \\leq N)\\) 为在上述过程中形成 \\(i\\) 个循环的所有可能排列 \\(p\\) 的 \\(f(p)\\) 的和。

找出 \\(b\_1, b\_2, \\ldots, b\_N\\) 的最大公约数，并以 \\({\\rm mod} \\ 998244353\\) 的形式打印出来。

### 约束条件

*   \\(1 \\leq N \\leq 10^5\\)
*   \\(1 \\leq a\_i \\leq 10^9\\)
*   输入中给出的所有数字都是整数

* * *

### 输入

输入采用以下格式从标准输入给出：

```plain
\\(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)\) 时形成的循环及其美丽度。