더 작은 문자열

정수 $\mathbf{K}$와 길이가 $\mathbf{N}$인 문자열 $\mathbf{S}$가 주어진다. 이 문자열은 영어 알파벳의 처음 $\mathbf{K}$개 글자에 해당하는 소문자로 이루어져 있다. 길이가 $\mathbf{N}$이고, $\mathbf{S}$보다 사전순으로 작으며, 영어 알파벳의 처음 $\mathbf{K}$개 글자에 해당하는 소문자로 이루어진 팰린드롬 문자열의 개수를 구한다.

순서가 있는 문자들 $a_1, a_2, \dots, a_n$로 구성된 문자열이 같은 길이의 다른 문자열 $b_1, b_2, \dots, b_n$보다 사전순으로 작다는 것은 $a_i < b_i$임을 뜻한다. 여기서 $i$는 두 문자열에서 문자가 서로 다른 첫 번째 인덱스이다. 예를 들어 다음 문자열들은 사전순으로 오름차순 정렬되어 있다: aaa, aab, aba, cab.

팰린드롬은 앞에서부터 읽어도 뒤에서부터 읽어도 같은 문자열이다. 예를 들어 anna, racecar, aaa, x는 모두 팰린드롬이지만, ab, frog, yoyo는 그렇지 않다.

그러한 문자열의 개수는 매우 클 수 있으므로, 답을 $10^9 + 7$로 나눈 나머지를 출력한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 문자열 $\mathbf{S}$는 영어 알파벳의 처음 $\mathbf{K}$개 글자에 해당하는 소문자로 이루어져 있다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 8$. $1 \le \mathbf{K} \le 5$.

테스트 세트 2

시간 제한: 10초. $1 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{K} \le 26$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 두 정수 $\mathbf{N}$와 $\mathbf{K}$가 주어진다. 두 번째 줄에는 소문자로 이루어진 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 1부터 시작하고, $y$는 사전순으로 더 작은 팰린드롬 문자열의 개수를 $10^9 + 7$로 나눈 나머지이다.

예제 케이스 #1에서 팰린드롬은 ["aa", "bb"]이다.

예제 케이스 #2에서 팰린드롬은 ["aaaaa", "aabaa", "aacaa", "aadaa", "aaeaa", "ababa", "abbba", "abcba"]이다.

예제 케이스 #3에서 팰린드롬은 ["a", "b", "c"]이다.