Chef and String

Chef has a string S consisting of N lowercase English alphabets. He has prepared a list L consisting of all non empty substrings of the string S. Now he asks you Q questions. To ith question, you need to count the number of ways to choose exactly Ki equal strings from the list L. As answer could be large you need to find it modulo 109+7. Input The first line of the input contains an integer T d