题目描述

今天是 YQH 的生日，她得到了 $n$ 个只包含小写字母的字符串 $s_i$ 作为生日礼物，第 $i$ 个字符串长度为 $a_i$。

YQH 对字符串非常感兴趣，她定义了函数 $f(s)$ 表示 $s$ 最小表示的开头元素的下标，下标从 $1$ 开始，如果有多个满足的元素则取下标最小的那个。例如，$f(\text{aaaa})=1,f(\text{babc})=2,f(\text{qweqweqwe})=3$，因为三个字符串的最小表示分别为 $\text{aaaa,abcb,eqweqweqw}$。如果你不知道最小表示法：请点击。

YQH 的字符串是有魔力的，只要使用一个魔咒，每个 $s_i$ 会等概率随机变成所有长度为 $a_i$ 的只包含小写字母的 $26^{a_i}$ 个字符串的其中一个。每次使用魔咒后，YQH 想记录下 $f(s_i)$，然而，她有些马虎，记录的顺序从 $f(s_1),f(s_2),\dots,f(s_n)$ 变成了 $f(s_n),f(s_1),f(s_2),\dots,f(s_{n-1})$ ，即向右循环移位一步。

YQH 的朋友 MY 注意到了这一情况，每次使用魔咒后，他都数出了多少个位置上的数没有记录错，记为 $c$，显然有 $c=\sum_{i=1}^n [f(s_i)=f(s_{(i\bmod n) +1})]$。但是 MY 厌倦了这个过程，他准备直接求出 $c$ 的期望值。

聪明的你一定知道 $\sum_{i=1}^n [f(s_i)=f(s_{(i\bmod n) +1})]$ 的期望值了，请把这个数目告诉 MY 吧。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

输出格式

输出一个整数表示 $c$ 的期望值对 $998244353$ 取模后的值。

样例

样例输入1

2
1 2

样例输出1

729486259

显然 $f(s_1)$ 恒为 $1$，$f(s_2)=1+[s_{2,1} > s_{2,2}]$，所以，$P([f(s_1)=f(s_2)])={351\over 676}$，所以 $E(\sum_{i=1}^n [f(s_i)=f(s_{(i\bmod n) +1})])={27\over 26}\equiv 729486259\pmod{998244353}$。

样例输入2

1
1000

样例输出2

1

显然 $f(s_1)$ 恒等于自身。

样例输入3

5
3 1 5 2 4

样例输出3

727907401

样例输入/输出4

见下发文件中 ex_hw4.in 和 ex_hw4.ans，样例 4 满足 $\text{subtask2}$ 的限制。

样例输入/输出5

见下发文件中 ex_hw5.in 和 ex_hw5.ans，样例 5 满足 $\text{subtask5}$ 的限制。

数据范围与提示

对于全部数据，保证 $1\le n,a_i\le 10^5$。

$\text{subtask1 10pts}$，$a_i\le 8$。

$\text{subtask2 20pts}$，保证 $a_i$ 全为质数。

$\text{subtask3 10pts}$，$n,a_i\le 1000$。

$\text{subtask4 20pts}$，$\sum a_i\le 10^5$。

$\text{subtask5 40pts}$，无特殊限制。

时间限制：$\texttt{1.5s}$

空间限制：$\texttt{256MB}$