23140번 - Minimal Cyclic Shift 다국어

문제

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円$.

제한

힌트