Description

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

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

To take part in a match, he divided all his players into $N$ groups, with $K$ players in each group. For the players in group $i$, their surname lengths are all $i$.

Now, he is going to plan the lineup combinations. A lineup has $N$ players, and the organizing committee has the following requirements for the team that plays:

• All players' surname lengths must be different.

• Each player's surname must be a contiguous substring of the surname of the player whose surname is longer than theirs by exactly one character.

Patrik wants to know the maximum number of teams that can be formed to play. Output the answer modulo $10^9+7$。

Input Format

The first line contains two integers $N, K$。

In the next $N$ lines, each line contains $K$ strings, which are the players' surnames. It is guaranteed that the strings in line $i$ have length $i$。

Output Format

Output one integer in one line: the maximum number of teams that can be formed, modulo $10^9+7$。

3 2
a b
ab bd
abc abd

5

3 3
a b c
aa ab ac
aaa aab aca

6

3 1
a
bc
def

0

Hint

Explanation of Sample $1$:

The following teams can be formed:

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

Constraints

For $100\%$ of the testdata, $1\le N\le 50$, $1\leq K\leq 1500$。

Translated by ChatGPT 5