H - Similar Strings
Earlgray
2
s
1024
MB
550
点
問題文
英小文字からなる長さの等しい文字列$X$と$Y$が似ているとは、$X$の先頭の文字と$Y$の先頭の文字が一致し、かつ$X$の末尾の文字と$Y$の末尾の文字が一致していることを指します。
英小文字からなる$N$個の文字列$S_1, S_2, . . . , S_N$に対して次を満たす$N$個の文字列 $T_1, T_2, . . . , T_N$ を考えます。
・$i = 1, 2, . . . , N$について、$|S_i| = |T_i|$が成り立つ。
・$T_1, T_2, . . . , T_N$をこの順に結合した文字列を並び替えることで、$S_1, S_2, . . . , S_N$をこの順に結合した文字列に等しくできる。
このような$T_1, T_2, . . . , T_N$として考えられるものすべてについて、$(S_iとT_iが似ているiの個数)$の $2$ 乗の総和を $998244353$ で割った余りを求めてください。
制約
- $1 \leq N \leq 2 \times 10^5$
- $|S_i| \geq 1\ (i = 1, 2, . . . N)$
- $\sum_{i = 1}^N |S_i| \leq 2 \times 10^5$
入力
$N$
$S_1$
$S_2$
$\vdots$
$S_N$
出力
答えを出力せよ。
入力例 1
2
tsg
live
出力例 1
252
条件を満たす$T_1,\ T_2$は $5040$ 通りあり、例えば $T_1=\rm{git},\ T_2=\rm{lvse}$ が考えられます。このとき、$S_2$と$T_2$は似ているため、$(S_iとT_iが似ているiの個数)$の $2$ 乗は $1$ です。同様にほかの$T_1,\ T_2$についても計算を行うことで、答えは $252$ と分かります。
入力例 2
1
ooooo
出力例 2
1
$T_1$として考えられるのは $T_1=\rm{ooooo}$ のみです。
入力例 3
3
theoretical
science
group
出力例 3
741100580
$998244353$ で割った余りを出力することに注意してください。