Prefix Partitioning in LQ Country

In the distant LQ country, every word is composed exclusively of the three characters $\tt{l}$, $\tt{q}$ and $\tt{b}$ (with ASCII codes $108$, $113$, and $98$, respectively). A magic dictionary contains $N$ words. In order to help memorize words faster, Xiaolan decides to partition the dictionary into $K$ classes by choosing $K$ distinct non‐empty prefixes with the following requirements:

1. Choose $K$ different non‐empty prefixes that occur in the dictionary (each chosen prefix must be a prefix of at least one word).
2. For every word in the dictionary, there must be exactly one chosen prefix that is a prefix of that word. (In other words, the $K$ chosen prefixes form a prefix–free set that covers every word exactly once.)
3. Each of the $K$ classes (i.e. the set of words having the same chosen prefix) is non–empty.

Your task is to count the number of ways to choose such a set of $K$ prefixes. Two ways are considered different if the sets of chosen prefixes differ. Since the answer can be very large, output it modulo $10^9+7$.

Formally, given a dictionary of $N$ words (each word a string over the alphabet {l, q, b}) and an integer $K$, count the number of sets $P$ of $K$ non–empty strings satisfying:

• For every $p\in P$, there exists at least one word in the dictionary with prefix $p$.
• For every word $w$ in the dictionary, there is exactly one $p\in P$ such that $p$ is a prefix of $w$.

Note that we do not allow the empty string as a prefix.

inputFormat

The first line contains two integers $N$ and $K$ ($1 \le N \le 10^5$, $1 \le K \le N$), representing the number of words in the dictionary and the required number of classes, respectively. Each of the next $N$ lines contains a non–empty string consisting only of the characters 'l', 'q' and 'b'. It is guaranteed that the total length of all words does not exceed $10^5$.

outputFormat

Output a single integer: the number of ways to choose $K$ prefixes to partition the dictionary as described, modulo $10^9+7$.

sample

1 1
l

1