Hasan and boring classes

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Hasan is a computer science student, he likes his study field, especially programming and algorithms, but he doesn’t like attending classes at all since they are very boring, especially that the quality of education in his college is extremely low, but sometimes he is forced to attend in order to maintain his attendance rate otherwise he will be prevented from doing final exams!
Currently Hasan is attending `communication skills` class and he is now feeling very bored especially that he thinks such course should not belong to a computer science program, luckily he remembered a problem that one of his friends has given him so he decided to spend the time thinking about it, the problem states:
Given a string S of length N of lower English letters, find how many strings T exists of length N of lower English letters such that T is palindrome and hamming distance between T and S is at most K. since the answer is large find the remainder modulo 10^{9} + 7
Since you also don’t like `communication skills` classes you decided to solve this problem too.
Input
The first line of the input contains an integer T denoting the number of test cases.
each testcase is described with two lines, the first line of each testcase contains two integers N and K.
The second line of each testcase will contains the string S of length N.
Output
For each test case, output a single line containing the answer to the testcase.
Constraints
 1 ≤ T ≤ 10,000
 1 ≤ N ≤ 300,000
 1 ≤ sum of N in all testcases ≤ 1,000,000
 0 ≤ K ≤ N
 String S will consist of English lower letters.
Example
Input: 2 3 2 abc 3 1 abc Output: 76 2
Explanation
in second testcase the only possible strings are "aba" and "cbc"
Author:  kingofnumbers 
Tester:  amrmahmoud 
Editorial  https://discuss.codechef.com/problems/PALHAM 
Tags  combinatorics, cook88, kingofnumbers, kingofnumbers, likecs, medium 
Date Added:  26052017 
Time Limit:  1 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. 