题目描述

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

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

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

输入格式

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

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

输出格式

输出一个整数表示答案。答案可能很大，请输出答案对 $1\,000\,000\,007$ 取模的值。

4 2
lqb
lql
qqq
qql

4

提示

样例说明

• 方案 1：$\tt{l}=\tt{lqb}, \tt{lql}$、$\tt{q}=\tt{qqq}, \tt{qql}$；
• 方案 2：$\tt{lq}=\tt{lqb}, \tt{lql}$、$\tt{q}=\tt{qqq}, \tt{qql}$；
• 方案 3：$\tt{l}=\tt{lqb}, \tt{lql}$、$\tt{qq}=\tt{qqq}, \tt{qql}$；
• 方案 4：$\tt{lq}=\tt{lqb}, \tt{lql}$、$\tt{qq}=\tt{qqq}, \tt{qql}$。

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

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq N \leq 10$，$1 \leq K \leq 5$；
• 对于 $50\%$ 的评测用例，$1 \leq N \leq 50$，$1 \leq K \leq 10$；
• 对于所有评测用例，$1 \leq N \leq 200$，$1 \leq K \leq 100$，$1 \leq$ 单词长度 $\leq 10$。