#P18586. P-P-Palindrome

P-P-Palindrome

P-P-Palindrome

给定 nn 个只含小写英文字母的字符串 S1,…,SnS_1,\ldots,S_n。

统计满足以下条件的有序对 (P,Q)(P,Q) 的数量:

  • P,QP,Q 均为非空回文串。
  • PP 和 QQ 各自至少在某个给定字符串中作为连续子串出现。它们可以来自不同的字符串。
  • 将 QQ 接在 PP 后面得到的 P+QP+Q 也是回文串。

这里回文串是指从左到右与从右到左读完全相同的字符串。

两个有序对不同,当且仅当它们的 PP 不同或 QQ 不同;同一个字符串出现多次不产生新的选择。允许 P=QP=Q,且不要求 P+QP+Q 在输入中出现。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行一个非空字符串,第 ii 行为 SiS_i。

输出格式

输出一个整数,表示满足要求的不同有序对数量。答案不取模。

数据范围

1≤n≤1061\le n\le10^6,1≤∣Si∣≤1061\le |S_i|\le10^6,∑i=1n∣Si∣≤106\sum_{i=1}^n |S_i|\le10^6。输入只包含一组数据。

样例输入 1

2
aaaa
aaa

样例输出 1

16

样例输入 2

3
abaaa
abbbba
bbbaba

样例输出 2

28

样例说明

第一组可选择的回文串为 a、aa、aaa、aaaa。任取两个拼接后仍为回文串,共有 4×4=164\times4=16 个有序对。