该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

在遥远的 $LQ$ 国，只存在三种字符：l、q 和 b (ASCII 码分别为 $108$、$113$、$98$)，所有的单词都由这三种字符组合而来。小蓝为了更加快速的记忆单词，决定将词典上所有的单词按照单词前缀将其分为 $K$ 类，具体的要求是:

• 1.选出 $K$ 个不同的单词前缀作为 $K$ 类；
• 2.对于字典上的每个单词，只能属于 $K$ 类中的某一个类，不能同时属于多个类；
• 3.对于 $K$ 类中的每个类，至少包含有一个单词。

现在已知字典上一共有 $N$ 个单词，小蓝想要知道将这 $N$ 个单词按照上述要求分为 $K$ 类，一共有多少种不同的方案。两个方案不同指的是两个方案各自选出的 $K$ 个单词前缀不完全相同。答案可能过大，所以你需要将答案对 $1000000007$ (即 $10^9+7$)取模后输出。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$；

接下来 $N$ 行，每行包含一个单词，由 l、q、b 三种字符组成。

输出格式

输出一个整数表示答案。答案可能很大，请输出答案对 $1000000007$ 取模的值。

样例

4 2
lqb
lql
qqq
qql

4

样例说明

• 方案 1：l=lqb,lql、q=qqq,qql;
• 方案 2：lq=lqb,lql、q=qqq,qql;
• 方案 3：l=lqb,lql、qq=qqq,qql;
• 方案 4：lq=lqb,lql、qq=qqq,qql。

以方案 1 为例，他表示选出的两类对应的前缀分别是 l 和 q，属于前缀 l 的单词有 lqb、lql，属于前缀 q 的单词有 qqq、qql，方案 1 将四个单词按照前缀分成了两类，且每类至少包含一个单词，每个单词仅属于一类，所以方案 1 满足题意。

评测用例规模与约定

对于 $30\%$ 的评测用例，$1≤N≤10$，$1≤K≤5$；

对于 $50\%$ 的评测用例，$1≤N≤50$，$1≤K≤10$；

对于所有评测用例，$1≤N≤200$，$1≤K≤100$，$1≤1≤单词长度≤10$。