F. 字符串缩写太多了！
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

八奈见杏菜是字符串低手。一日，佳树给来到温水家的杏菜出了一道题。

我们定义：

  • 一个缩写是取有序的若干字符串的首字母拼接形成的。如：abc bcd def 的缩写为 abd。
  • 一个缩写的方案数是通过选取若干个字符串按一定顺序取得该缩写的方案数。如：如果给定三个字符串 aaa aab baa，那么缩写 aab 的方案数是 $$$2$$$，分别为 aaa aab baa 和 aab aaa baa。

现在给定 $$$n$$$ 个各不相同的英文小写字母字符串，求出这些字符串能构成的所有缩写的方案数之和，答案对 $$$10^9+7$$$ 取模。

然而杏菜对这题无能为力，但她知道你是字符串高手，于是请你帮她写了这题。

$$$\texttt{T}_{\texttt{\^{}}}\texttt{T}$$$
Input

第一行一个整数 $$$n$$$，表示字符串的数量 $$$(1 \leq n \leq 10^5)$$$。

接下来的 $$$n$$$ 行，每行是一个只有小写英文字母的字符串。保证所有字符串各不相同。

保证所有读入的字符串长度和不大于 $$$10^6$$$

Output

对于每组测试用例，输出一个整数，表示所有缩写的方案数之和，答案对 $$$10^9+7$$$ 取模。

Examples
Input
3
aaa
aab
bba
Output
15
Input
5
ya
na
mi
an
naa
Output
325
Note

对于样例：

  • 缩写 a 的方案有 $$$2$$$ 种：aaa、aab。
  • 缩写 b 的方案有 $$$1$$$ 种：bba。
  • 缩写 aa 的方案有 $$$2$$$ 种：aaa aab、aab aaa。
  • 缩写 ab 的方案有 $$$2$$$ 种：aaa bba、aab bba。
  • 缩写 ba 的方案有 $$$2$$$ 种：bba aaa、bba aab。
  • 缩写 aab 的方案有 $$$2$$$ 种：aaa aab bba、aab aaa bba。
  • 缩写 aba 的方案有 $$$2$$$ 种：aaa bba aab、aab bba aaa。
  • 缩写 baa 的方案有 $$$2$$$ 种：bba aaa aab、bba aab aaa。

共有 $$$2+1+2+2+2+2+2+2=15$$$ 种方案