Problem Description

Niwango-kun has \(N\\) chickens. Each chicken is identified by a number from \(1\\) to \(N\\), and the size of the \(i\\)-th chicken is a positive integer \(a\_i\\).

The \(N\\) chickens decided to form some circles by holding hands. The way to form circles is represented by a permutation \(p\\) of \(1, \\ldots, N\\), where chicken \(i\\) holds the left hand of chicken \(p\_i\\). Chickens can also hold their own hands.

A circle containing chicken \(i\\) is defined as the set of chickens \(p\_i, p\_{p\_i}, \\ldots, p\_{\\ddots\_i} = i\\). When all \(N\\) chickens hold hands, it can be proven that they are divided into several circles.

The beauty \(f(p)\\) of the way to form circles is defined as the product of the sizes of the smallest chickens in each circle.

For \(1 \\leq i \\leq N\\), let \(b\_i\\) be the sum of \(f(p)\\) for all permutations \(p\\) that form \(i\\) circles.

Find the greatest common divisor of \(b\_1, \\ldots, b\_N\\) modulo \(998244353\\).

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2
4 3

Sample Output #1

3

Sample Input #2

4
2 5 2 5

Sample Output #2

2

Notes/Hints

Constraints

• \(1 \\leq N \\leq 10^5\\)
• \(1 \\leq a\_i \\leq 10^9\\)
• All numbers given in the input are integers.

Sample Explanation 1

For \(N = 2, a = \\\[ 4, 3 \\\]\\). For the permutation \(p = \\\[ 1, 2 \\\]\\), there are two circles consisting of chicken \(1\\) and chicken \(2\\) respectively, so \(f(\\\[1, 2\\\]) = a\_1 \\times a\_2 = 12\\). For the permutation \(p = \\\[ 2, 1 \\\]\\), there is one circle consisting of chicken \(1\\) and chicken \(2\\), and the smallest chicken in the circle is \(a\_2 = 3\\), so \(f(\\\[2, 1\\\]) = a\_2 = 3\\). From this, \(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 Explanation 2

Even if chickens have the same size, they are distinguishable, so there are always \(N!\\) permutations. The following figure shows the way to form circles and their beauty for \(p = (2, 1, 4, 3), p = (3, 4, 1, 2)\\).

见题面 Input 部分

见题面 Output 部分