Smaller Strings

Problem

You are given an integer $\mathbf{K}$ and a string $\mathbf{S}$ of length $\mathbf{N}$, consisting of lowercase letters from the first $\mathbf{K}$ letters of the English alphabet. Find the number of palindrome strings of length $\mathbf{N}$ which are lexicographically smaller than $\mathbf{S}$ and consist of lowercase letters from the first $\mathbf{K}$ letters of the English alphabet.

A string composed of ordered letters $a_1, a_2, \dots, a_n$ is lexicographically smaller than another string of the same length $b_1, b_2, \dots, b_n$ if $a_i < b_i$, where $i$ is the first index where characters differ in the two strings. For example, the following strings are arranged in lexicographically increasing order: aaa, aab, aba, cab.

A palindrome is a string that is the same written forwards and backwards. For example, anna, racecar, aaa and x are all palindromes, while ab, frog and yoyo are not.

As the number of such strings can be very large, print the answer modulo $10^9 + 7$.

Input

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

Each test case consists of two lines. The first line contains two integers $\mathbf{N}$ and $\mathbf{K}$. The second line contains a string $\mathbf{S}$ of length $\mathbf{N}$, consisting of lowercase letters.

Output

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from 1) and $y$ is the number of lexicographically smaller palindrome strings modulo $10^9 + 7$.

Limits

Memory limit: 1 GB.
$1 \le \mathbf{T} \le 100$.
The string $\mathbf{S}$ consists of lowercase letters from the first $\mathbf{K}$ letters of the English alphabet.

Test Set 1

Time limit: 20 seconds.
$1 \le \mathbf{N} \le 8$.
$1 \le \mathbf{K} \le 5$.

Test Set 2

Time limit: 10 seconds.
$1 \le \mathbf{N} \le 10^5$.
$1 \le \mathbf{K} \le 26$.

Sample

Sample Input

3
2 3
bc
5 5
abcdd
1 5
d

Sample Output

Case #1: 2
Case #2: 8
Case #3: 3

In Sample Case #1, the palindromes are ["aa", "bb"].

In Sample Case #2, the palindromes are ["aaaaa", "aabaa", "aacaa", "aadaa", "aaeaa", "ababa", "abbba", "abcba"].

In Sample Case #3, the palindromes are ["a", "b", "c"].