GEN - Text Generator

LoadingTime has been given a task these days. He is required to write a tool called Text Generator. This software is widely used among the kids who are under seven. It generates an article with the size of a given number L for users. If an article contains at least one word which the users know, we consider it readable. Now, LoadingTime wants to know, how many readable articles can it generates, and he can improve his Text Generator. Could you help him??

Input

The input contains multiple test cases.

The first line of each test case contains two integer N (1 <= N <= 10), L (1 <= L <= 1000000). The following N lines contain N words representing the words known by the users. All the words and the generated article only contain uppercase letters, and the length of each word is not greater than 6.

Output

For each test case, your program should output a integer as LoadingTime required. As the number could be quite large, you only need to print the answer modulo 10007.

Example

Input:
2 2
A
B
2 10000
ABC
B

Output:
100
5960

Added by:Bin Jin
Date:2007-07-05
Time limit:1.386s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:

hide comments
2022-12-19 10:09:13
Why constrain reasonable constants?And there're no exact statement about how much test cases it have. How can I come to consider whether constant optimization is needed? Such trick doesn't make sense.
2012-10-13 19:07:18 cybie
I dont understand the Description, what is L used for?
2011-07-17 03:48:40 Tony Beta Lambda
This problem needs light constant optimization.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.