Problem K

Palindrome Again
Input: Standard Input

Output: Standard Output

You are given a string S of length N. Can you find a string P which satisfies the following conditions?

1. Length of P will be N

2. Distance between S and P will be less than or equal to K

3. P will be a palindrome.

4. P can contain only characters ‘a’, ‘b’, …, ‘z’

You have to calculate, in how many ways you can choose P. This number can be very large, so print the answer modulo 1000000000 (10⁹).

Notes:

- A string is a sequence of characters. For this problem consider that all strings can contain only ‘a’, ‘b’, …, ‘z’, i.e. 26 available characters.

- The length of the string is defined by the number of characters in the string. For example, length of “abcba” is 5.

- A string is called palindrome when it is the same string when written from forwards or backwards. For example – “abcba”, “abba”, “a” are palindrome but “abc” is not a palindrome.

- Distance between two string of same length is the number of mismatches of corresponding characters. For example, distance between “abcb” and “bcba” is 4 because no character of first string matches to the character of the corresponding index of second string, but distance between “abc” and “cba” is 2.

Input

Input starts with an integer T (T is around 5000), the number of test cases.

Each test case consists of two lines. First line contains two integers N(1≤N≤1000) and K (0≤K≤1000). Second line contains a string S of length N. S contains only characters from ‘a’, ‘b’, …, ‘z’.

Output

For each test case output the number of test cases followed by the number of ways the string can be chosen modulo 1000000000 (10⁹). See sample output for exact format.

Sample Input	Output for Sample Input
3 3 2 kxk 4 1 addc 4 3 Addc	Case 1: 51 Case 2: 2 Case 3: 76

---

Problemsetter: Arifuzzaman Arif

Special Thanks  Manzurur Rahman Khan