Ani 是一位年轻且鲁莽的学生。有一天，他收到了一份非常奇怪的数学作业。

在作业中，他得到了 $n$ 个字符串 $s_1, s_2, \dots, s_n$，它们的长度分别为 $a_1, a_2, \dots, a_n$。

定义 $f(s)$ 为字符串 $s$ 的字典序最小循环移位开始的位置。由于该位置可能不唯一，$f(s)$ 被定义为满足条件的最小位置。例如，$f(\text{“qweqweqwe”}) = 3$，因为 $s = \text{“qweqweqwe”}$ 的字典序最小循环移位是 $\text{“eqweqweqw”}$，而它在 $s$ 中开始的最小可能位置是第 3 位，即第一个字母 $\text{“e”}$ 所在的位置。

作业要求按顺序写下 $f(s_1), f(s_2), \dots, f(s_n)$。但由于 Ani 的鲁莽和截止日期的临近，他错误地按 $f(s_n), f(s_1), \dots, f(s_{n-1})$ 的顺序写下了答案。

Ani 在提交答案后才意识到这一点。现在他只记得 $a_1, a_2, \dots, a_n$。假设给定的字符串仅包含小写英文字母，且由老师均匀随机生成，你需要帮助他计算他作业中正确答案数量的期望值，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示 Ani 作业中给出的字符串数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)，用空格分隔，表示字符串的长度。

输出格式

输出一行一个整数：Ani 作业中正确答案数量的期望值，对 $998\,244\,353$ 取模。

形式化地，可以证明正确答案数量的期望值可以表示为一个分数 $p/q$，其中 $p$ 和 $q$ 是互质的非负整数。你需要输出 $p \cdot q^{-1} \pmod{998\,244\,353}$ 的值。

样例

样例输入 1

5
3 1 5 2 4

样例输出 1

727907401

样例输入 2

1
100000

样例输出 2

1