Dream Team Formation

This problem is translated from COCI 2019/2020 Contest #6 (Trener).

Patrik, a record‐holder for sleeping, dreams of becoming the captain of his favorite team. In his dream, he divides his players into N groups with each group containing K players. In the i-th group, every player's surname has length exactly i.

The team formation rules for a match are as follows:

• A team consists of exactly one player from each group (i.e. N players in total).
• Since all players come from different groups, the surname lengths in a team are all distinct.
• For every player from group i (1 ≤ i ≤ N - 1), his surname must appear as a contiguous substring in the surname of the player from group i+1. Note that since the surname in group i+1 has length exactly one more than that in group i, there are only two possible positions where the substring can occur.

Each player can be used in at most one team. Patrik wants to know the maximum number of valid teams he can form. Since the answer can be large, output it modulo \(10^9+7\).

inputFormat

The first line contains two integers N and K (1 ≤ N, K ≤ some reasonable limit).

This is followed by N groups. For i = 1 to N, there are K lines; each line contains a string representing the surname of a player from group i. It is guaranteed that each string has length exactly i and consists of lowercase English letters.

outputFormat

Output a single integer — the maximum number of teams that can be formed satisfying the conditions, modulo \(10^9+7\).

sample

2 2
a
b
ab
bb

2