在一次最小表示法相关的作业中，有 $n$ 个字符串 $s_1, s_2, \dots, s_n$，其长度分别为 $a_1, a_2, \dots, a_n$。

定义 $f(s)$ 为字符串 $s$ 的字典序最小循环移位的起始位置。由于这样的起始位置可能不唯一，因此 $f(s)$ 取最小的可能位置。例如对于字符串 cbacba，它的最小循环移位是 acbacb，选取的起始位置是 $3$（这里使用 1-index）。

作业的要求是按顺序写下 $f(s_1), f(s_2), \dots, f(s_n)$。然而，由于小 A 的粗心，他错误地按照以下顺序写下了答案：$f(s_n), f(s_1), f(s_2), \dots, f(s_{n-1})$。

假设这些字符串的每个字符是由老师等概率随机生成的，仅包含小写英文字母。你需要帮助小 A 计算他的作业中期望正确答案的数量，对 $998244353$ 取模。

输入格式

第一行包含一个整数 $n$，表示作业中给出的字符串数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示字符串的长度。

输出格式

输出一个整数，表示答案。

样例输入 1

5
3 1 5 2 4

样例输出 1

727907401

样例输入/输出 2~4

见下发文件。

数据范围

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^5$。