더 작은 문자열

정수 K와 길이 N인 문자열 S가 주어진다. S는 영어 알파벳의 처음 K개 소문자로만 이루어져 있다. 길이 N이면서 S보다 사전순으로 작고, 영어 알파벳의 처음 K개 소문자로만 이루어진 회문 문자열의 개수를 구하라.

문자 a1, a2, …, an으로 이루어진 문자열이 같은 길이의 문자열 b1, b2, …, bn보다 사전순으로 작다는 것은, 두 문자열에서 문자가 처음으로 달라지는 위치 i에 대해 ai < bi라는 뜻이다. 예를 들어 다음 문자열들은 사전순으로 증가하는 순서로 나열되어 있다: aaa, aab, aba, cab.

회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다. 예를 들어 anna, racecar, aaa, x는 모두 회문이고, ab, frog, yoyo는 회문이 아니다.

이런 문자열의 개수는 매우 클 수 있으므로 답을 109 + 7로 나눈 나머지를 출력하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 두 정수 N과 K가 주어진다. 둘째 줄에는 길이 N인 문자열 S가 주어지며, 소문자로 이루어져 있다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 사전순으로 더 작은 회문 문자열의 개수를 109 + 7로 나눈 나머지이다.

• 1 ≤ T ≤ 100.
• 문자열 S는 영어 알파벳의 처음 K개 소문자로 이루어져 있다.

샘플 케이스 #1에서 회문은 ["aa", "bb"]이다.

샘플 케이스 #2에서 회문은 ["aaaaa", "aabaa", "aacaa", "aadaa", "aaeaa", "ababa", "abbba", "abcba"]이다.

샘플 케이스 #3에서 회문은 ["a", "b", "c"]이다.