Jerry has been given an assignment in his ICS class to program an ai that can generate crazy sentences. He has decided to form sentences from a word bank, but to make sure that his output is a good size, will require the total number of letters (not spaces) to be exactly letters. Furthermore, to make sure his program has enough variety, Jerry would like to know how many sentences are possible.
Sentences are a list of words separated by spaces, and can use each word from the word bank any number of times. Two sentences are distinct if they have a different number of words or there exists any such that the -th word in the first and second sentences aren't equal. In other words, if two sentences are different if they don't use the exact same words in the exact same order.
Constraints
Each word will have at most 200 characters.
Input Specification
The first line contains two integers and , the number of words in the word bank, and the total number of characters in a sentence.
The next lines each contain one string made up only of lowercase characters. The words are also guaranteed to be distinct.
Output Specification
One integer, the number of possible sentences, modulo
Sample Input
4 6
hi
game
bat
you
Sample Output
7
Sample Explanation
The possible sentences are:
hi hi hi
hi game
bat you
bat bat
you bat
you you
game hi
Note that words can be used multiple times. There are 7 sentences made from these words with 6 total letters.
Comments