题目描述

给定 $n$ 个字符串 $s_1,s_2,\cdots,s_n$。

设 $M(s,t)$ 表示 $s$ 中等于 $t$ 的连续子串的个数，$s+t$ 表示 $s,t$ 拼接在一起形成的字符串。

计算：

$$\sum_{i=1}^n\sum_{j=1}^n\sum_{x=1}^n\sum_{y=1}^n\sum_{p=1}^n\sum_{q=1}^nM(s_i+s_x+s_p,s_j+s_y+s_q)$$

答案对 $2^{64}$ 取模。

输入格式

从文件 $\textit{hvd.in}$ 中读入数据。

第一行一个整数 $n$。

接下来 $n$ 行每行一个字符串。

输出格式

输出到文件 $\textit{hvd.out}$ 中。

一行一个整数表示答案。

样例 #1

样例输入 #1

1
a

样例输出 #1

1

$i,j,x,y,p,q$ 全部为 $1$，此时 $s_i+s_x+s_p=\texttt{aaa}$，$s_j+s_y+s_q=\texttt{aaa}$，前者有 $1$ 个子串等于后者。

样例 #2

样例输入 #2

2
a
ab

样例输出 #2

12

样例 #3

样例输入 #3

5
a
aa
aaa
abba
bbab

样例输出 #3

2191

样例 #4

见下发文件中的 $\textit{hvd/hvd4.in}$ 与 $\textit{hvd/hvd4.ans}$。

该样例满足子任务 $4$ 的限制。

样例 #5

见下发文件中的 $\textit{hvd/hvd5.in}$ 与 $\textit{hvd/hvd5.ans}$。

该样例满足子任务 $5$ 的限制。

样例 #6

见下发文件中的 $\textit{hvd/hvd6.in}$ 与 $\textit{hvd/hvd6.ans}$。

该样例满足子任务 $6$ 的限制。

样例 #7

见下发文件中的 $\textit{hvd/hvd7.in}$ 与 $\textit{hvd/hvd7.ans}$。

该样例满足子任务 $7$ 的限制。

提示

对字符串 $s$，设 $|s|$ 为其长度。设 $S=\sum_{i=1}^n|s_i|$。

对于 $100\%$ 的数据，$1\leq n,S\leq 3\times 10^5$，字符集为所有小写英文字母，字符串互不相同。

子任务	$n$	$S$	字符集	特殊性质
$1$	$\leq 5$	$\leq 20$
$2$	$\leq 10$	$\leq 300$
$3$	$\leq 100$	$\leq 5000$
$4$	$\leq 1000$
$5$		$\leq 2\times 10^5$	$\{\texttt a\}$
$6$	$\leq 2\times 10^5$		$\{\texttt a,\texttt b\}$	A
$7$				B
$8$	$\leq 1000$
$9$	$\leq 2\times 10^5$
$10$	$\leq 3\times 10^5$

• 特殊性质 A：字符串的每一个位置从字符集中等概率随机选取。
• 特殊性质 B：字符串长度 $\leq 10$。

评测时开启合理的子任务依赖，每个子任务分值均为 $10$ 分。