March Break Contest '22 Problem 2 - Crazy Sentences

View as PDF

Submit solution

Points: 7
Time limit: 1.5s
Memory limit: 128M

Author:
Problem type

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 K 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 i such that the i-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

1\le N\le 100

1\le K\le 10^5

Each word will have at most 200 characters.

Input Specification

The first line contains two integers N and K, the number of words in the word bank, and the total number of characters in a sentence.

The next N lines each contain one string made up only of lowercase characters. The N words are also guaranteed to be distinct.

Output Specification

One integer, the number of possible sentences, modulo 10^9+7

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

There are no comments at the moment.