You are given an integer and a string of length , consisting of lowercase letters from the first letters of the English alphabet. Find the number of palindrome strings of length which are lexicographically smaller than and consist of lowercase letters from the first letters of the English alphabet.
A string composed of ordered letters is lexicographically smaller than another string of the same length if , where 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 .
输入格式
The first line of the input gives the number of test cases, . test cases follow.
Each test case consists of two lines. The first line contains two integers and . The second line contains a string of length , consisting of lowercase letters.
输出格式
For each test case, output one line containing Case #: followed by , where is the test case number (starting from ) and is the number of lexicographically smaller palindrome strings modulo .
样例
样例输入 1
3
2 3
bc
5 5
abcdd
1 5
d
样例输出 1
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"].
Limits
.
The string consists of lowercase letters from the first letters of the English alphabet.
