Time Limit: 1000 MS    Memory Limit: 131072 K 


Description

约翰家里有很多奶牛,住在牛棚最东边的奶牛要给另外一个奶牛写情书,他向约翰要了一个文本生成器——这个生成器可以生成一篇长度固定的文章,但是这个数据生成器出了问题, 生成的文章中的每个字符串都是完全随机的。如果一篇文章中至少包含了奶牛了解的一个单词,那这篇文章就是可以被接受的(包含是指单词为文章的子串)。 现在你需要帮助奶牛指出生成的文本中可读文本的数量,这样它可以撩妹成功。

Input

输入数据的第一行是一个case数 输入数据的第二行包含两个整数,分别是奶牛了解的单词总数N(<=60),文本生成器的固定长度为M; 一下N行,每一行包含一个奶牛知道的单词。这里所有单词及文本的长度不会超过100,并且只可能包含英文大写字母A.....Z。

Output

每行一个整数,表示可能的文章总数。只需要知道结果%10007的值。

Sample Input

1 2 2 A B

Sample Output

100