All submissions for this problem are available.
Given a string S of length N, consisting of lowercase English alphabets from ‘a’ to ‘z’,
you have to select three non overlapping substrings of S, such that number of a’s in the string made by concatenating the three substrings are greater than or equal to M.
You have to find the number of ways of selecting three such substrings. Output your answer modulo (10^9 + 7)
First line contains T, the number of test cases.
Each test case consists of 2 lines, first line contains the string S and the second line contains the integer M.
The output consists of T lines, such that i-th line represents the output of the i-th test case.
- Sum of length of strings over all test cases ≤ 5000
- 0 ≤ M ≤ 5000
- Length(S) > 0
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions