COCI '19 Contest 6 #5 Trener

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

At this point we already know that students love to sleep. Patrik is a record holder in this category. He wakes up only when he needs to eat or if he wishes to play FIFA 20. Therefore, his dreams usually revolve around football. In his last dream, he found himself in the role of a football manager of his favourite team – GNK Dinamo Zagreb.

His job is to select N players that will defend the blue colors in the next season, but the board has some peculiar requests. They are:

  • All players must have surnames of distinct lengths.
  • Surname of a player must appear as a continuous subsequence of surnames of all players whose surnames are longer.

To make his job easier, Patrik divided the potential players in N buckets such that players in i-th bucket have exactly i letters in their surname. In each of these buckets there are exactly K players. Patrik wants to know in how many distinct ways (modulo 10^9 + 7) can he choose the players for his squad while also conforming to the given requests.

Input

The first line contains two integers N (1 \le N \le 50) and K (1 \le K \le 1\,500).

Each of the next N lines contains K not necessarily distinct surnames of players. The surnames of players in i-th of those lines consist of exactly i lowercase letters from the English alphabet.

Output

In the only line you should output the answer from the task description.

Scoring

Subtask Score Constraints
1 22 N \le 5 and K \le 10
2 33 N \le 50 and K \le 100
3 55 No additional constraints.

Sample Input 1

3 2
a b
ab bd
abc abd

Sample Output 1

5

Explanation of Sample Output 1

Patrik can choose the following teams: (a, ab, abc), (a, ab,
abd), (b, ab, abc), (b, ab, abd) and (b, bd, abd).

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

Comments

There are no comments at the moment.