Chef and String

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
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 i^{th} question, you need to count the number of ways to choose exactly K_{i} equal strings from the list L. As answer could be large you need to find it modulo 10^{9}+7.
Input
The first line of the input contains an integer T denoting the number of test cases. First line of each test case contains two spaceseparated integers N and Q denoting the length of the string S and amount of questions. The next line of each test case contains a single string S. Each of the next Q lines contains a single integer K_{i}.
Output
For each test case, output Q lines, each line should contain one integer  amount of ways to choose exactly K_{i} equal strings from the list L.
Constraints
Subtask 1: (10 points)
 1 ≤ T ≤ 100
 1 ≤ N ≤ 5
 1 ≤ Q ≤ 5
 1 ≤ K_{i} ≤ 5
Subtask 2: (20 points)
 T = 1
 1 ≤ N ≤ 500
 1 ≤ Q ≤ 10^{5}
 1 ≤ K_{i} ≤ 10^{9}
Subtask 3: (70 points)
 T = 1
 1 ≤ N ≤ 5000
 1 ≤ Q ≤ 10^{5}
 1 ≤ K_{i} ≤ 10^{9}
Example
Input: 1 5 4 ababa 2 1 3 4 Output: 7 15 1 0
Explanation
L = {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba", "abab", "baba", "ababa"}.
 k_{1} = 2: There are seven ways to choose two equal strings ("a", "a"), ("a", "a"), ("a", "a"), ("b", "b"), ("ab", "ab"), ("ba", "ba"), ("aba", "aba").
 k_{2} = 1: We can choose any string from L (15 ways).
 k_{3} = 3: There is one way to choose three equal strings  ("a", "a", "a").
 k_{4} = 4: There are no four equal strings in L .
Author:  antoniuk1 
Editorial  http://discuss.codechef.com/problems/CHSTR 
Tags  antoniuk1, combinatorics, june15, medium, suffixarray, zfunction 
Date Added:  6042015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions