背景

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

题目描述

给定 $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$。

输出格式

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

3
ab
ac
ad

6

提示

【样例解释】

完全图 $K_3$ 有 $3$ 棵生成树，每棵树包含两条边。三条边权值均为 $1$，每棵树权值和为 $2$，总和为 $6$。

【数据范围】

本题采用捆绑测试，即你需要通过该子任务的所有测试点才能获得该子任务的分数。

::cute-table{tuack}

对于 $100 \%$ 的数据，$s_i$ 均为小写字母。