407735: GYM102888 J 期望步数

给定 n 个非空的字符串，s₁, s₂, ..., s_n，小 A（第一步）先等概率地在 s₁, s₂, ..., s_n 上的某一个串上开始进行走动。每次走动的过程如下

1. 等概率地选择当前字符串 s_i，除自身以外的一个非空子串 s_i[x: y]，即 s_i 的第 x 到第 y 个字符这一子串（满足 1 ≤ x ≤ y ≤ |s| 且 y - x + 1 < |s|）。 若不存在这样的子串（即当前字符串长度等于 1），则停止走动。
2. 若在给定的 n 个字符串中，存在某个字符串 s_j，满足 s_j = s_i[x: y]，则走到字符串 s_j 上；若存在多个相同的、可走到的字符串，则等概率地走到其中一个上。 若在给定的 n 个字符串中，不存在字符串 s_j，满足 s_j = s_i[x: y]，则停止走动。

比如，aabbcc 经过一步可以走到 abbc 这个串上，也可以走到 a 这个串上。不过走到这两个串的概率不同，因为原串存在两个 a 这个子串。

请问经过若干次这样的操作后，小 A 停止时，经过的串的个数的期望是多少？

答案对 998, 244, 353 取模。具体地说，设 M = 998, 244, 353，可以证明答案一定可以被表示成一个既约分数 ，其中 p, q 均为整数且 。输出满足 0 ≤ x < M 且 x·q ≡ p ± od{M} 的整数 x。例如答案为 时，应该输出 499, 122, 177。

保证输入字符串中的字符都是小写英文字母。

第一行一个整数 n (1 ≤ n ≤ 10⁵)，表示总共有 n 个字符串。

接下来 n 行，每行一个非空的字符串 s_i，代表题目中所说的 s_i 字符串，满足 ，即字符串总长度不超过 10⁶。

保证输入字符串中的字符都是小写英文字母。

一个整数，表示小 A 停止时，经过的串的个数的期望，答案对 998, 244, 353 取模。

2
a
aa

499122178

3
a
aa
aaa

399297743

5
aa
a
ab
abba
aaaa

798595484

需要特别注意，选择的子串指的是除自身以外的一个非空子串。

对于第一个样例：

第一步，等概率( )地选择第一个串 a 或者第二个串 aa。

若选择第一个串 a，则过程结束。共经过 1 个串（1 步）。

若选择第二个串 aa，等概率地选择其中的子串 a 或 a，由于这 n 个串中存在一个 a 串，走到第一个串上。然后由于 a 除了本身之外没有其他子串，走动过程结束。共经过 2 个串（2 步）。

答案是 。

对于第二个样例：

对于第三个串，因为共有 2 个 aa 子串和 3 个 a 子串，所以会有 概率走到第一个串上， 概率走到第二个串上。

答案是 。

对于第三个样例：

对于第三个串，因为共有 1 个 a 子串和 1 个 b 子串，而且不存在 b 子串，所以有 概率走到第一个串， 的概率停止。

类似地，abba 有 的概率走到 ab，有 的概率走到 a，有 的概率停止。

答案是 。