시간 제한메모리 제한제출정답맞힌 사람정답 비율
서브태스크 참고 (추가 시간 없음) 1024 MB (추가 메모리 없음)30161560.000%

문제

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 a1, a2, …, an is lexicographically smaller than another string of the same length b1, b2, …, bn if ai < bi, 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 109 + 7.

입력

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.

출력

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 109 + 7.

제한

• 1 ≤ T ≤ 100.
• The string S consists of lowercase letters from the first K letters of the English alphabet.

시간 제한: 20 초

• 1 ≤ N ≤ 8.
• 1 ≤ K ≤ 5.

시간 제한: 10 초

• 1 ≤ N ≤ 105.
• 1 ≤ K ≤ 26.

예제 입력 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"].

채점 및 기타 정보

• 예제는 채점하지 않는다.