시간 제한메모리 제한제출정답맞은 사람정답 비율
1.5 초 256 MB0000.000%

문제

Ani is a young and reckless student. One day, he got a really weird math homework.

In the homework, he was given $n$ strings $s_1, s_2, \ldots, s_n$ with length $a_1, a_2, \ldots, a_n$, respectively.

Define $f(s)$ as the position where the lexicographically minimal cyclic shift of $s$ starts. Since it may not be unique, $f(s)$ is defined as the minimal such position. For example, $f($"qweqweqwe"$) = 3$, because the lexicographically minimal cyclic shift of $s = $"qweqweqwe" is "eqweqweqw", and the minimal possible position where it starts in $s$ is position $3$ where the first letter "e" is located.

The homework was to write down $f(s_1), f(s_2), f(s_3), \ldots, f(s_n)$, in this order. But Ani's recklessness and the approaching of the deadline caused him to write the answers in the order $f(s_n), f(s_1), f(s_2), \ldots, f(s_{n-1})$.

Ani had not realized this until he submitted his answers. Now he can only remember $a_1, a_2, \ldots, a_n$. Assuming the given strings contain only lowercase English letters and were generated uniformly at random by the teacher, you need to help him calculate the expected number of correct answers in his homework modulo $998\,244\,353$.

입력

The first line of input contains an integer $n$ ($1 \le n \le 10^5$), the number of strings given in Ani's homework.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$) separated by spaces, indicating the lengths of the strings.

출력

Print a single line with an integer: the expected number of correct answers in Ani's homework modulo $998\,244\,353$.

Formally, it can be shown that the expected number of correct answers can be represented as a fraction $p / q$ for some coprime non-negative integers $p$ and $q$. You have to print the value $p \cdot q^{-1} \bmod 998\,244\,353$.

예제 입력 1

5
3 1 5 2 4

예제 출력 1

727907401

예제 입력 2

1
100000

예제 출력 2

1