时之魔法
题号：NC205558
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

吉他君的乐谱上有 n 个由小写字母组成的字符串，第 i 个字符串长度为 len_i 。
这 n 个字符串一共有 后缀(重复算多个后缀)，现在键盘手定义主唱随着乐谱上的伴奏歌唱发动的魔法值是：。
其中 suf_i, suf_j 分别是 个后缀中的一个后缀，i, j 可以相同， 是这两个后缀的最长公共前缀的长度。
由于这是属于三个人的歌曲，所以乐谱上的字符串会有几率发生一些变动。其中，第 i 个字符串会有 p_i 的概率反转，现在请你求出最终发动的魔法值在模 998244353 意义下的期望。

输入描述:

第一行一个数 n ，表示乐谱上字符串的个数。
第二行，共 n 个 [0,998244352] 之间的数，p_i ，表示第 i 个字符串反转的概率在模 998244353 意义下的值。
第三行到第 n+2 行，每行若干个字符，第 i 行表示第 i-2 个字符串。

输出描述:

一个数，表示题意中终发动的魔法值在模 998244353 意义下的期望。
示例1

输入

复制 
2
0 0
aaa
abb

输出

复制 
28

说明

对于第一个样例，所有串都没有概率反转，所以：
对于第一个串中的后缀 a：
|lcp(a,a)|=1, |lcp(a,aa)|=1,|lcp(a,aaa)|=1,|lcp(a,abb)|=1，贡献为 4。
对于第一个串中的后缀 aa ：
|lcp(aa,a)|=1, |lcp(aa,aa)|=2,|lcp(aa,aaa)|=2,|lcp(aa,abb)|=1， 贡献为 6
对于第一个串中的后缀 aaa：
|lcp(aaa,a)|=1, |lcp(aaa,aa)|=2,|lcp(aaa,aaa)|=3,|lcp(aaa,abb)|=1，贡献为 7。
对于第二个串中的后缀 b：
|lcp(b,b)|=1, |lcp(b, bb)|=1， 贡献为 2。

示例2

输入

复制 
3
166374059 332748118 499122177
abcbdea
eeaadbc
aaabb

输出

复制 
110916194

说明

无可奉告

备注:

数据范围：。