我们已经知道学生们非常热爱睡觉。Patrik 是这个领域的纪录保持者。他只有在需要吃东西或者想玩 FIFA 20 的时候才会醒来。因此，他的梦境通常都围绕着足球展开。在最近的一个梦中，他发现自己成为了他最喜欢的球队——萨格勒布迪纳摩（GNK Dinamo Zagreb）的足球经理。

他的任务是选择 $N$ 名球员在下个赛季中为球队效力，但董事会提出了一些奇特的要求。它们是：

• 所有球员的姓氏长度必须互不相同。
• 一个球员的姓氏必须是所有姓氏比其更长的球员姓氏的连续子序列（即子串）。

为了简化工作，Patrik 将候选球员分成了 $N$ 个桶，使得第 $i$ 个桶中的球员姓氏长度恰好为 $i$。每个桶中恰好有 $K$ 名球员。Patrik 想要知道，在满足上述要求的情况下，他有多少种不同的方式（模 $10^9 + 7$）来选择他的阵容。

输入格式

第一行包含两个整数 $N$ ($1 \le N \le 50$) 和 $K$ ($1 \le K \le 1500$)。

接下来的 $N$ 行，每行包含 $K$ 个不一定不同的球员姓氏。其中第 $i$ 行的球员姓氏恰好由 $i$ 个英文小写字母组成。

输出格式

在唯一的一行中输出题目描述中所求的答案模 $10^9 + 7$ 的结果。

子任务

样例

输入样例 1

3 2
a b
ab bd
abc abd

输出样例 1

5

输入样例 2

3 3
a b c
aa ab ac
aaa aab aca

输出样例 2

6

输入样例 3

3 1
a
bc
def

输出样例 3

0

说明

样例 1 解释：Patrik 可以选择以下阵容：(a, ab, abc)，(a, ab, abd)，(b, ab, abc)，(b, ab, abd) 和 (b, bd, abd)。