题目描述

翁老师有 $n$ 个字符串 $s_1,s_2,s_3,\cdots,s_n$。

翁老师对一个字符串在另一个字符串里作为连续子串出现的情况很感兴趣，例如 ab 就在 abaab 中作为连续子串出现了两次。

他用 $f(s,t)$ 表示 $s$ 在 $t$ 中以一个连续子串出现的次数，例如 $f(\texttt{ab},\texttt{abaab})=2$。

现在翁老师想对 $s_1,s_2,s_3,\cdots,s_n$ 中的任意三个串 $s_i,s_j,s_k$，求出 $f(s_i,s_j)\times f(s_j,s_k)\times f(s_k,s_i)$ 的结果，并将这个结果对所有的 $i,j,k$ 求和。其中 $i,j,k$ 可以相等，也不要求它们从小到大排列。

请你帮翁老师求出这个总和，并输出答案对 $10^9+7$ 取模的结果。

输入格式

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

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

输出格式

一行一个整数表示答案。

3
aa
aa
ab

9

其余样例

附件

数据规模与约定

设 $|s|$ 为字符串 $s$ 的长度，则对于所有数据，满足 $1\leq n,\sum |s_i|\leq 10^6$，字符串包含所有 ASCII 可见字符（ASCII $33\sim 126$）。