P6221 [COCI 2019/2020 #6] Trener

This problem translation comes from [LOJ3270](https://loj.ac/problem/3270)。

**Translated from [COCI 2019/2020 Contest #6](https://hsin.hr/coci/archive/2019_2020/) T5.** ***[Trener](https://hsin.hr/coci/archive/2019_2020/contest6_tasks.pdf)*** 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$。

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 one integer in one line: the maximum number of teams that can be formed, modulo $10^9+7$。

#### 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$。 |Task ID|Special Restriction|Score| |:-:|:-:|:-:| |$0$|Sample.|$0$| |$1$|$N=5,K=10$|$20$| |$2$|$N=50,K=100$|$30$| |$3$|No special restriction.|$50$| Translated by ChatGPT 5