超简单题1--烤串

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

XX爱烤串成痴。。于是他打算在自己的烧烤铺子里举办一个串串大赛,铺子里有n种烤串,每种都有无限多个提供,每个烤串上都有字符编号,比赛要求在这n种串中选择m个连接起来,连接规则是:如果a串的后缀(不小于2)是b串的前缀,那么就可以把b接到a的后面。举办人不能不知道一共可以组成多少个不同的串呀,可是他又数学不好,你能帮他解决这个问题吗?

Input

多组输入,第一行输入两个整数n,m(n<=50,m<=10^9)之后n行,每行一个字符串,表示烤串上的字符标号,字符串长度小于100,全是英文小写字母,并且保证字符串不重复

Output

输出一个整数,最终可以组成的不同串的个数。输出结果对1e9+7取余。

Sample Input

2 2
aba
bab

Sample Output

4

Hint


Source