### 问题描述 在遥远的 $\text{LQ}$ 国，只存在三种字符：$\text{l、q }$和 $\text{b}$ (ASCII 码分别为 $108、113、98$)，所有的单词都由这三种字符组合而来。小蓝为了更加快速的记忆单词，决定将词典上所有的单词按照单词前缀将其分为 $K$ 类，具体的要求是: 1) 选出 $K$ 个不同的单词前缀作为 $K$ 类； 2) 对于字典上的每个单词，只能属于 $K$ 类中的某一个类，不能同时属于多个类； 3) 对于 $K$ 类中的每个类，至少包含有一个单词。 现在已知字典上一共有 $N$ 个单词，小蓝想要知道将这 $N$ 个单词按照上述要求分为 $K$ 类，一共有多少种不同的方案。两个方案不同指的是两个方案各自选出的 $K$ 个单词前缀不完全相同。答案可能过大，所以你需要将答案对 $1000000007$ (即 $10^9 + 7$)取模后输出。 ### 输入格式 输入的第一行包含两个整数 $N$ 和 $K$； 接下来 $N$ 行，每行包含一个单词，由 $\text{l、q、b}$ 三种字符组成。 ### 输出格式 输出一个整数表示答案。答案可能很大，请输出答案对 $1000000007$ 取模的值。 ### 样例输入 ``` 4 2 lqb lql qqq qql ``` ### 样例输出 ``` 4 ``` ### 样例说明 方案 1：$\text{l=lqb,lql、q=qqq,qql}$; 方案 2：$\text{lq=lqb,lql、q=qqq,qql}$; 方案 3：$\text{l=lqb,lql、qq=qqq,qql}$; 方案 4：$\text{lq=lqb,lql、qq=qqq,qql}$。 以方案 1 为例，他表示选出的两类对应的前缀分别是 $\text{l}$ 和 $text{q}$，属于前缀 $\text{l}$ 的单词有 $\text{lqb、lql}$，属于前缀 $\text{q}$ 的单词有 $\text{qqq、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$。