Background

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

Problem Description

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$.

Input Format

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

Output Format

Output one integer, representing the answer.

3
ab
ac
ad

6

Hint

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}

For $100 \%$ of the testdata, each $s_i$ consists of lowercase letters.

Translated by ChatGPT 5