Problem Description

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

A string composed of ordered letters $a_1, a_2, \ldots, a_n$ is lexicographically smaller than another string of the same length $b_1, b_2, \ldots, 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 Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

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

Output Format

For each test case, output one line containing Case #$x$: followed by $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$.

3
2 3
bc
5 5
abcdd
1 5
d

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

Hint

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"].

Limits

$1 \le T \le 100$.

The string $S$ consists of lowercase letters from the first $K$ letters of the English alphabet.

Test Set $1$

$1 \le N \le 8$.

$1 \le K \le 5$.

Test Set $2$

$1 \le N \le 10^5$.

$1 \le K \le 26$.