E - Cyclic GCDs /

### 問題文

ニワンゴくんは $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$ 羽のニワトリたちは何個かの輪に分割できることが証明できます。

$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 ]$ である。

### 入力例2

4
2 5 2 5


### 出力例2

2


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

Score : 1000 points

### Problem Statement

Niwango-kun has $N$ chickens as his pets. The chickens are identified by numbers $1$ to $N$, and the size of the $i$-th chicken is a positive integer $a_i$.

$N$ chickens decided to take each other's hand (wing) and form some cycles. The way to make cycles is represented by a permutation $p$ of $1, \ldots , N$. Chicken $i$ takes chicken $p_i$'s left hand by its right hand. Chickens may take their own hand.

Let us define the cycle containing chicken $i$ as the set consisting of chickens $p_i, p_{p_i}, \ldots, p_{\ddots_i} = i$. It can be proven that after each chicken takes some chicken's hand, the $N$ chickens can be decomposed into cycles.

The beauty $f(p)$ of a way of forming cycles is defined as the product of the size of the smallest chicken in each cycle. Let $b_i \ (1 \leq i \leq N)$ be the sum of $f(p)$ among all possible permutations $p$ for which $i$ cycles are formed in the procedure above.

Find the greatest common divisor of $b_1, b_2, \ldots, b_N$ and print it ${\rm mod} \ 998244353$.

### Constraints

• $1 \leq N \leq 10^5$
• $1 \leq a_i \leq 10^9$
• All numbers given in input are integers

### Input

Input is given from Standard Input in the following format:

$N$
$a_1$ $a_2$ $\ldots$ $a_N$


### Sample Input 1

2
4 3


### Sample Output 1

3


In this case, $N = 2, a = [ 4, 3 ]$.

For the permutation $p = [ 1, 2 ]$, a cycle of an only chicken $1$ and a cycle of an only chicken $2$ are made, thus $f([1, 2]) = a_1 \times a_2 = 12$.

For the permutation $p = [ 2, 1 ]$, a cycle of two chickens $1$ and $2$ is made, and the size of the smallest chicken is $a_2 = 3$, thus $f([2, 1]) = a_2 = 3$.

Now we know $b_1 = f([2, 1]) = 3, b_2 = f([1, 2]) = 12$, and the greatest common divisor of $b_1$ and $b_2$ is $3$.

### Sample Input 2

4
2 5 2 5


### Sample Output 2

2


There are always $N!$ permutations because chickens of the same size can be distinguished from each other.

The following picture illustrates the cycles formed and their beauties when $p = (2, 1, 4, 3)$ and $p = (3, 4, 1, 2)$, respectively.