P16780 ⌈Xzy OI R1 T2⌋ Chengcheng Edges.

A short and to-the-point statement~~how could it be a bad statement~~.

Given $n$ strings $s_1, s_2, \dots, s_n$. Construct a complete graph $G$ with vertices numbered $1 \sim n$. The weight of edge $(i, j)$ is defined as $\text{LCP}(s_i, s_j)$, i.e., the length of the longest common prefix of the two strings. Define the weight of a spanning tree $T$ as the sum of the weights of all edges in $T$. Find the sum of the weights of all spanning trees of $G$, and output the answer modulo $10^9+7$.

The first line contains an integer $n$. The next $n$ lines each contain a string $s_i$.

Output one integer, representing the answer.

**Sample Explanation** The complete graph $K_3$ has $3$ spanning trees, and each tree contains two edges. All three edges have weight $1$, so the sum of edge weights in each tree is $2$, and the total sum is $6$. --- **Constraints** **This problem uses bundled subtasks, which means you must pass all test points in a subtask to get the score for that subtask.** ::cute-table{tuack} | Subtask | Score | $1 \le n \le$ | $1 \le \sum \lvert s_i \lvert \le$ | Special Restriction | | :---: | :---: | :---: | :---: | :---: | | $1$ | $10$ | $8$ | $50$ | None | | $2$ | $20$ | $300$ | $5000$ | None | | $3$ | $20$ | $2000$ | ^ | None | | $4$ | $15$ | $10^5$ | $2\times 10^6$ | All strings are exactly the same | | $5$ | $35$ | ^ | ^ | None | For $100 \%$ of the testdata, each $s_i$ consists of lowercase letters. Translated by ChatGPT 5