13391339 SUSTech Online Judge
Problem 1339 --[Bouns] You Shall not AK

1339: [Bouns] You Shall not AK

Time Limit: 8 Sec  Memory Limit: 256 MB
Submit: 162  Solved: 15
[Submit][Status][Web Board]

Description

Given n strings containing only lowercase letters, and the \(i_{th}\)  string is \(s_i\). \(f(s,t)\) represent the maximum i satisfy \(s_{1...i} = t_{|t|-i+1...|t|}\), and \(f(s,t) = 0\) if such i doesn't exist. Please calculate:\(\sum_{i=1}^n\sum_{j=1}^n(i \cdot j \cdot f(s_i,s_j)) \ (\bmod 998244353)\).

Input

The first line is the integer n \(( 1 \leq n \leq 100000 )\). 

The following n lines contains one string \(s_i\) \((1 \leq |s_i|, 1 \leq i \leq n, \sum_{i=1}^n|s_i| \leq 1000000 )\).

Output

One line an integer, representing the answer.

Sample Input

2
ab
aba

Sample Output

20

HINT

Source

 

[Submit][Status]