题目描述

译自 COCI 2019/2020 Contest #6 T5. Trener

我们已经知道了学生们喜欢睡觉。Patrik 是这一记录的保持者。在最后一个梦中，他发现自己成为了他最喜欢的球队的队长。

为了参加一场比赛，他把自己的所有球员分为 $N$ 组，每组 $K$ 名球员，对于第 $i$ 组的球员，他们的姓氏长度都为 $i$。

现在，他要开始规划上场的球员组合了。一个组合有 $N$ 名球员，并且组委会对上场的球队还有以下要求：

1. 所有球员的姓氏长度必须不同。
2. 所有球员的姓氏必须为其他姓氏比他长一个字符的球员的连续子串。

Patrik 想知道，自己最多能把这些球员分为多少支可以上场的队伍。答案对 $10^9+7$ 取模。

---

输入格式

输入第一行为两个整数 $N$, $K$。

接下来的 $N$ 行，每行 $K$ 个字符串，为球员的姓氏，保证第 $i$ 行的字符串长度为 $i$。

---

输出格式

输出一行一个整数为最多分出的队伍支数，答案对 $10^9+7$ 取模。

---

样例 1

输入：

3 2
a b
ab bd
abc abd

输出：

5

说明：可以分为如下队伍：
$(a, ab, abc)$, $(a, ab, abd)$, $(b, ab, abc)$, $(b, ab, abd)$, $(b, bd, abd)$。

---

样例 2

输入：

3 3
a b c
aa ab ac
aaa aab aca

输出：

6

---

样例 3

输入：

3 1
a
bc
def

输出：

0

---

数据范围与提示

对于 $100\%$ 的数据：

• $1 \le N \le 50$，
• $1 \le K \le 1500$。

各子任务限制如下：

任务编号	特殊限制	分值
1	$N=5$, $K=10$	20
2	$N=50$, $K=100$	30
3	无特殊限制	50

---