In an assignment related to the minimal representation of strings, there are $n$ strings $s_1, s_2, \dots, s_n$ with lengths $a_1, a_2, \dots, a_n$ respectively.

Define $f(s)$ as the starting position of the lexicographically smallest cyclic shift of string $s$. Since such a starting position might not be unique, $f(s)$ is defined as the smallest possible position. For example, for the string cbacba, its minimal cyclic shift is acbacb, and the chosen starting position is $3$ (using 1-based indexing).

The requirement for the assignment is to write down $f(s_1), f(s_2), \dots, f(s_n)$ in order. However, due to Little A's carelessness, he incorrectly wrote down the answers in the following order: $f(s_n), f(s_1), f(s_2), \dots, f(s_{n-1})$.

Assume that each character of these strings is generated uniformly and independently at random by the teacher, consisting only of lowercase English letters. You need to help Little A calculate the expected number of correct answers in his assignment, modulo $998244353$.

Input

The first line contains an integer $n$, representing the number of strings in the assignment.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the lengths of the strings.

Output

Output an integer representing the answer.

Examples

Input 1

5
3 1 5 2 4

Output 1

727907401

Input 2~4

See the provided files.

Constraints

For all data, $1 \leq n \leq 10^5$, $1 \leq a_i \leq 10^5$.