P16845 [GKS 2021 #C] Smaller Strings

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$.

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$`: ` 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$.

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$.