题目描述
我们已经知道了学生们喜欢睡觉。Patrik 是这一记录的保持者。在最后一个梦中,他发现自己成为了他最喜欢的球队的队长。
为了参加一场比赛,他把自己的所有球员分为 $N$ 组,每组 $K$ 名球员,对于第 $i$ 组的球员,他们的姓氏长度都为 $i$。
现在,他要开始规划上场的球员组合了。一个组合有 $N$ 名球员,并且组委会对上场的球队还有有以下要求:
所有球员的姓氏长度必须不同。
所有球员的姓氏必须为其他姓氏比他长一个字符的球员的子串。
Patrik 想知道,自己最多能把这些球员分为多少支可以上场的队伍。答案对 $10^9+7$ 取模。
输入格式
输入第一行为两个整数 $N,K$。
接下来的 $N$ 行,每行 $K$ 个字符串,为球员的姓氏,保证第 $i$ 行的字符串长度为 $i$。
输出格式
输出一行一个整数为最多分出的队伍支数,答案对 $10^9+7$ 取模。
样例 #1
样例输入 #1
3 2
a b
ab bd
abc abd
样例输出 #1
5
样例 #2
样例输入 #2
3 3
a b c
aa ab ac
aaa aab aca
样例输出 #2
6
样例 #3
样例输入 #3
3 1
a
bc
def
样例输出 #3
0
提示
样例 $1$ 说明:
可以分为如下队伍:
(a, ab, abc), (a, ab,abd), (b, ab, abc), (b, ab, abd), (b, bd, abd)
。
数据范围:
对于 $100\%$ 的数据,$1\le N\le 50$,$1\leq K\leq 1500$。
任务编号 | 特殊限制 | 分值 |
---|---|---|
$0$ | 为样例 | $0$ |
$1$ | $N=5,K=10$ | $20$ |
$2$ | $N=50,K=100$ | $30$ |
$3$ | 无特殊限制。 | $50$ |