"Crimson Squadron, engage. Avenge this land."

题目描述

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

设 $f(s,t)$ 为 $s$ 在 $t$ 中以一个连续子串出现的次数。

求：

$\sum_{i=1} ^n {\sum_{j=1}^n{\sum_{k=1}^n{f(s_i,s_j)f(s_j,s_k)f(s_k,s_i)}}}$

答案对 $10^9 +7 $ 取模。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，第 $i$ 行一个字符串表示 $s_i$ 。

输出格式

一行一个整数表示答案。

样例 #1

样例输入 #1

3
aa
aa
ab

样例输出 #1

9

设 $|s|$ 为字符串 $s$ 的长度，则对于所有数据，满足 $\sum|s| \le 10^6$，字符串包含所有 ASCII 可见字符。