Devu and good strings

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A string str is called a good string if there does not exist three difference indices i, j, k such that i, j, k are consecutive three terms of an arithmetic progression and str[i] = str[j] = str[k].
You are given a string s and two integers K, A. You have to find the number of good strings t with alphabet size A (i.e. if A = 1, then string can only have a's and if A = 2, string can only contain 'a' or 'b'. e.g. if A = 2, t can be aa, ab, bb etc., for A = 3, string can only contain 'a', 'b' and 'c', i.e. it can be aab bac, bbb, cbb etc.) of length s such that hamming distance between strings s and t is less than or equal to K. As the answer could be very large, print answers modulo 10^{9} + 7.
Hamming distance between two strings of same size is defined as the number of indices where their corresponding characters differ. Formally, for two strings s, t of length N, hamming distance will be number of indices 1 ≤ i ≤ N such that s[i] != t[i].
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 For each test case, first line will contain two integers A, K.
 The second line of each test case will contain the string s.
Output
 For each test case, output a single line corresponding to the answer of the problem.
Constraints
 1 ≤ T ≤ 50
 0 ≤ K ≤ s
Subtask
Subtask 1 (10 points)
 1 ≤ s ≤ 50, A = 1
Subtask 2 (20 points)
 1 ≤ s ≤ 12, 1 ≤ A ≤ 3
Subtask 3 (30 points)
 1 ≤ s ≤ 50, A = 2
Subtask 4 (40 points)
 1 ≤ s ≤ 50, A = 3
Example
Input: 2 1 0 a 2 2 aba Output: 1 5
Explanation
Example case 1. Only string of length 1 and alphabet size 1 will be 'a'. Hamming distance of "a" with "a" is zero which is ≤ 1. So answer is 1.
Example case 2. There can be total 8 strings. 6 of them are good. aaa and bbb are not good, remaining all are good. From the 6 good strings, bab has a hamming distance of 3, remaining other 5 have hamming distance ≤ 2. Hence answer is 5.
Author:  admin2 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/DEVGOSTR 
Tags  admin2, april16, arithmetic, easymedium, hammingdist 
Date Added:  2032016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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
HELP
If you are still having problems, see a sample solution here. 