G - Concat Two by Two
Earlgray
2
s
1024
MB
600
点
問題文
$N$ 個の英小文字からなる文字列 $S_1, S_2, \dots, S_N$ が与えられます。また、 文字列 $s,t$ に対し $cat(s,t)$ を文字列 $s,t$ をこの順に連結したものと定義します。
$1$ 以上 $N$ 以下の整数の組 $(i,j,k,l)$ であって、 $cat(S_i,S_j)=cat(S_k,S_l)$ を満たすものの個数を$998244353$ で割った余りを求めてください。
制約
- $N$ は整数
- $1 \le N \le 5 \times 10^5$
- $S_i$ は英小文字からなる文字列
- $1 \le |S_i |$
- $|S_1|+|S_2|+ \dots + |S_N| \le 5 \times 10^5$
入力
$N$
$S_1$
$S_2$
$\vdots$
$S_N$
出力
答えを $1$ 行に出力せよ．
入力例 1
5
t
tsg
tsgst
st
sgst
出力例 1
27
入力例 2
5
bj
mitsubachi
rho
shiomusubi
zeta
出力例 2
25
入力例 3
20
ab
ab
ab
ab
ab
ab
ab
ab
abab
abab
abab
abab
abab
ababab
ababab
ababab
abababab
abababab
ababababab
abababababab
出力例 3
23668