题目描述

LoadingTime 最近接到一个任务：编写一个名为 Text Generator 的工具。这个软件被很多七岁以下的小朋友使用，它可以为用户生成一篇长度为给定整数 L 的文章。

如果一篇文章中至少包含一个用户认识的单词，那么我们认为这篇文章是可读的。

现在，LoadingTime 想知道：Text Generator 一共能生成多少篇可读文章，以便改进他的工具。你能帮助他吗？

这里的文章可以看作一个长度为 L 的大写英文字母串。如果某个用户认识的单词作为连续子串出现在文章中，则这篇文章可读。

输入格式

输入包含多组测试数据，直到文件结束 EOF。

每组测试数据第一行包含两个整数 N 和 L：

接下来 N 行，每行包含一个单词，表示用户认识的单词。

所有单词以及生成的文章都只包含大写英文字母。

输出格式

对于每组测试数据，输出一行一个整数，表示长度为 L 的可读文章数量。

由于答案可能很大，只需要输出答案对 10007 取模后的结果。

2 2
A
B
2 10000
ABC
B

100
5960

提示

• 保证：
  • 1 <= N <= 10
  • 1 <= L <= 1000000
  • 单词长度 1~6
  • 单词只含大写字母
  • 每组内单词互不相同