Good strings

3.7

11 votes
Dynamic Programming, 2D dynamic programming, Algorithms
Problem

Given a string S of length N consisting of only lower case alphabets. Print the total count of good strings. A string is called good if:-

- its length is N and consists of only lower case alphabets.
- it mismatches with S at exactly K different indexes.
- it is lexicographically smaller than S.

Since the answer could be large print it with modulo 109+7.

 Input format

  • The first line contains T denoting the number of test cases.
  • The first line of each test case contains integers N and K, denoting the size of the length of the S and mismatch count.
  • The next line contains S.

Output format

Print the number of total possible good strings. Since the answer could be large print it with modulo 109+7.

Constraints

1T5000
1N105
1K20

The sum of N over all test cases does not exceed 2105

Sample Input
1
4 1
abcd
Sample Output
6
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

All good strings are abcc,abcb,abca,abbd,abad,aabd.

Editor Image

?