题目描述

给定一个整数 $K$ 和一个长度为 $N$ 的字符串 $S$，$S$ 由英文字母表前 $K$ 个小写字母组成。求有多少个长度为 $N$ 的回文串，其字典序小于 $S$，并且仅由英文字母表前 $K$ 个小写字母组成。

由有序字母 $a_1, a_2, \dots, a_n$ 组成的字符串在字典序上小于另一个等长的字符串 $b_1, b_2, \dots, b_n$，如果存在第一个位置 $i$ 使得 $a_i < b_i$。例如，以下字符串按字典序递增排列：aaa、aab、aba、cab。

回文串是指正着读和反着读都相同的字符串。例如，anna、racecar、aaa 和 x 都是回文串，而 ab、frog 和 yoyo 不是。

由于这样的字符串数量可能非常大，请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例由两行组成。第一行包含两个整数 $N$ 和 $K$。第二行包含一个长度为 $N$ 的字符串 $S$，由小写字母组成。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是字典序更小的回文串的数量对 $10^9 + 7$ 取模的结果。

3
2 3
bc
5 5
abcdd
1 5
d

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

提示

在样例 #1 中，回文串有 ["aa", "bb"]。

在样例 #2 中，回文串有 ["aaaaa", "aabaa", "aacaa", "aadaa", "aaeaa", "ababa", "abbba", "abcba"]。

在样例 #3 中，回文串有 ["a", "b", "c"]。

限制条件

$1 \le T \le 100$。

字符串 $S$ 由英文字母表前 $K$ 个小写字母组成。

测试集 1

$1 \le N \le 8$。

$1 \le K \le 5$。

测试集 2

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

$1 \le K \le 26$。

翻译由 DeepSeek V4 Pro 完成