Today is YQH's birthday, and she received $n$ strings $s_i$ consisting only of lowercase letters as birthday gifts. The length of the $i$-th string is $a_i$.

YQH is very interested in strings. She defines a function $f(s)$ as the index of the starting element of the minimal representation of $s$, with indices starting from $1$. If there are multiple such elements, the smallest index is taken. For example, $f(\text{aaaa})=1, f(\text{babc})=2, f(\text{qweqweqwe})=3$, because the minimal representations of these three strings are $\text{aaaa, abcb, eqweqweqw}$ respectively. If you are unfamiliar with the minimal representation: please click here.

YQH's strings are magical. Whenever a spell is cast, each $s_i$ randomly transforms into one of the $26^{a_i}$ possible strings of length $a_i$ consisting of lowercase letters, with each string being equally likely. After casting the spell, YQH wants to record $f(s_i)$. However, she is a bit careless, and the recording order changes from $f(s_1), f(s_2), \dots, f(s_n)$ to $f(s_n), f(s_1), f(s_2), \dots, f(s_{n-1})$, which is a cyclic right shift by one position.

YQH's friend MY noticed this situation. After each spell is cast, he counts how many positions were recorded correctly, denoted as $c$. Clearly, $c = \sum_{i=1}^n [f(s_i) = f(s_{(i \bmod n) + 1})]$. MY is tired of this process and wants to calculate the expected value of $c$.

You, being clever, surely know the expected value of $\sum_{i=1}^n [f(s_i) = f(s_{(i \bmod n) + 1})]$. Please tell MY this value.

Input

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_i$.

Output

Output the expected value of $c$ modulo $998244353$.

Examples

Input 1

2
1 2

Output 1

729486259

Note 1

Clearly $f(s_1)$ is always $1$, and $f(s_2) = 1 + [s_{2,1} > s_{2,2}]$. Therefore, $P([f(s_1) = f(s_2)]) = \frac{351}{676}$, so $E(\sum_{i=1}^n [f(s_i) = f(s_{(i \bmod n) + 1})]) = \frac{27}{26} \equiv 729486259 \pmod{998244353}$.

Input 2

1
1000

Output 2

1

Note 2

Clearly $f(s_1)$ is always equal to itself.

Input 3

5
3 1 5 2 4

Output 3

727907401

Input 4

See ex_hw4.in and ex_hw4.ans in the provided files. Example 4 satisfies the constraints of $\text{subtask2}$.

Input 5

See ex_hw5.in and ex_hw5.ans in the provided files. Example 5 satisfies the constraints of $\text{subtask5}$.

Constraints

For all data, it is guaranteed that $1 \le n, a_i \le 10^5$.

$\text{subtask1 10pts}$: $a_i \le 8$.

$\text{subtask2 20pts}$: $a_i$ are all prime numbers.

$\text{subtask3 10pts}$: $n, a_i \le 1000$.

$\text{subtask4 20pts}$: $\sum a_i \le 10^5$.

$\text{subtask5 40pts}$: No special constraints.