Problem Description

Translated from COCI 2019/2020 Contest #6 T5. Trener

We already know that students love to sleep. Patrik holds the record for this. In his last dream, he found himself as the captain of his favorite team.

To participate in a match, he divided all his players into $N$ groups, each containing $K$ players. For the players in the $i$-th group, their surnames all have a length of $i$.

Now, he is starting to plan the combinations of players for the match. A combination consists of $N$ players, and the organizing committee has the following requirements for the teams that play:

• All players' surnames must have different lengths.
• All players' surnames must be a continuous subsequence of the surname of another player whose surname is one character longer.

Patrik wants to know the maximum number of teams he can form that can play, modulo $10^9+7$.

Input Format

The first line of input contains two integers $N$ and $K$.

The next $N$ lines each contain $K$ strings, which are the surnames of the players. The strings in the $i$-th line are guaranteed to have a length of $i$.

Output Format

Output a single integer, which is the maximum number of teams that can be formed, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3 2
a b
ab bd
abc abd

Sample Output #1

5

Sample Input #2

3 3
a b c
aa ab ac
aaa aab aca

Sample Output #2

6

Sample Input #3

3 1
a
bc
def

Sample Output #3

0

Notes/Hints

Sample 1 Explanation:

The teams can be formed as follows:

(a, ab, abc), (a, ab, abd), (b, ab, abc), (b, ab, abd), (b, bd, abd).

Data Range:

For $100\%$ of the data, $1 \le N \le 50$, $1 \leq K \leq 1500$.

见题面 Input 部分

见题面 Output 部分