P16780 ⌈Xzy OI R1 T2⌋ 成成边

简言意骇的题面~~怎么能是坏题面呢~~。

给定 $n$ 个字符串 $s_1, s_2, \dots, s_n$。构造一个完全图 $G$，顶点编号 $1 \sim n$，边 $(i, j)$ 的权值定义为 $\text{LCP}(s_i, s_j)$，即两个字符串的最长公共前缀的长度。 定义一棵生成树 $T$ 的权值为 $T$ 中所有边的权值之和。 求 $G$ 的所有生成树的权值之和，答案对 $10^9+7$ 取模。

第一行一个整数 $n$。 接下来 $n$ 行，每行一个字符串 $s_i$。

输出一个整数，表示答案。

**【样例解释】** 完全图 $K_3$ 有 $3$ 棵生成树，每棵树包含两条边。三条边权值均为 $1$，每棵树权值和为 $2$，总和为 $6$。 --- **【数据范围】** **本题采用捆绑测试，即你需要通过该子任务的所有测试点才能获得该子任务的分数。** ::cute-table{tuack} | 子任务 | 分值 | $1 \le n \le$ | $1 \le \sum \lvert s_i \lvert \le$ | 特殊限制 | | :---: | :---: | :---: | :---: | :---: | | $1$ | $10$ | $8$ | $50$ | 无 | | $2$ | $20$ | $300$ | $5000$ | 无 | | $3$ | $20$ | $2000$ | ^ | 无 | | $4$ | $15$ | $10^5$ | $2\times 10^6$ | 所有字符串完全相同 | | $5$ | $35$ | ^ | ^ | 无 | 对于 $100 \%$ 的数据，$s_i$ 均为小写字母。