|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|서브태스크 참고 (추가 시간 없음)||1024 MB (추가 메모리 없음)||9||5||5||71.429%|
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:
A palindrome is a string that is the same written forwards and backwards. For example,
x are all palindromes, while
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.
시간 제한: 20 초
시간 제한: 10 초
3 2 3 bc 5 5 abcdd 1 5 d
Case #1: 2 Case #2: 8 Case #3: 3
In Sample Case #1, the palindromes are
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"].