A41139.最小表示

小栋是个字符串爱好者。

对于一个长度为 $n$ 的字符串 $S=S_1S_2...S_n$ ，我们定义 $R(S,i)$ 为 $S$ 的 $i$ 次循环移位，即

$R(S,i)=S_iS_{i+1}...S_nS_1...S_{i-1}$

例如 $R(abc,1)=abc,R(abc,2)=bca$ ，在 $R(S,1)...R(S,n)$ 中，小栋希望你能求出字典序最小的一个，这样的 $i$ 可能有很多个，记 $F(S)$ 为他们中最小的一个，如 $F(qweqweqwe)=3$ 。

当然，只要求 $F(S)$ 可能太简单，所以小栋给了你 $m$ 个字符串 $S_1,S_2,...,S_m$ 。

当然，只要求这些的 $F(S_i)$ 依旧过于简单，于是你草草完成了任务，提交时一不小心把他们的顺序打乱成了 $F(S_m),F(S_1),F(S_2),...,F(S_{m-1})$ 。

当然，只要求有多少个答案正确未免太简单，由于年代久远，你只记得这些字符串的长度了。

不妨假设每个字符串都仅包含小写英文字母且均匀随机生成，小栋希望你能求出提交的答案中期望有多少个正确答案。

第一行一个整数 $m$ ，表示字符串的数量。

第二行 $m$ 个空格隔开的整数 $n_1,...,n_m$ ，依次表示 $m$ 个字符串的长度。

一行一个整数 $x$ ，表示期望正确答案数对 $998244353$ 取模的结果。

即假设期望为 $\frac{p}{q}$ ，则 $x$ 为满足 $xq\equiv p(mod\ 998244353)$ 的最小非负整数。

由基本的数论知识我们可以知道，$x$ 应该取 $pq^{998244353-1}$ 。

在编程中，你应该使用快速幂来加速计算，即将求 $x^y$ 的问题转变为 $x^{y/2}$ ，递归处理。

数据规模与约定

对于 $20\%$ 的数据，$m=2,n_i\leq 3$ 。

对于 $40\%$ 的数据，$m\leq 300,n_i\leq 300$ 。

对于另外 $20\%$ 的数据，$m\leq 5000$ ， $n_i$ 均为质数。

对于前 $80\%$ 的数据，$m\leq 5000,n_i\leq 5000$ 。

对于 $100\$$ 的数据，$m,n_i\leq 10^5$ 。