회문 삭제

최근에는 단어와 문자열을 이용한 게임이 매우 인기 있다. 이제 Edsger는 자신만의 비슷한 새 게임을 만들려고 한다. 지금까지 그가 생각해 낸 내용은 다음과 같다.

Edsger의 새 게임은 회문 삭제라고 한다. 이 게임의 플레이어에게는 길이가 $\mathbf{N}$인 문자열이 주어진다. 그런 다음 다음 과정을 $\mathbf{N}$번 수행한다.

• 현재 문자열에서 인덱스 하나를 균등한 확률로 무작위 선택한다.

• 해당 인덱스의 문자를 삭제한다. 그러면 문자가 하나 더 적은 새 문자열을 얻게 된다.

• 새 문자열이 회문이면 축하하는 의미로 사탕 한 조각을 먹는다.

이제 Edsger는 시작 문자열이 주어졌을 때 게임 중에 먹게 될 사탕 수의 기댓값이 얼마인지 궁금해한다.

제한

시간 제한: 30초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 20$. 문자열 $\mathbf{S}$은 영문 소문자로만 구성된다.

테스트 세트 1

$2 \le \mathbf{N} \le 8$.

테스트 세트 2

$2 \le \mathbf{N} \le 400$.

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

각 테스트 케이스의 첫 번째 줄에는 문자열의 길이를 나타내는 정수 $\mathbf{N}$이 주어진다.

각 테스트 케이스의 두 번째 줄에는 영문 소문자로 구성된 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $E$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $E$는 게임 중에 먹게 될 사탕 수의 기댓값이다.

$E$은 다음과 같이 소수 $10^9+7$ ($1000000007$)로 나눈 나머지로 계산해야 한다. 테스트 케이스의 답을 기약분수 $\frac{p}{q}$로 나타낸다. 그러면 수 $E$는 모듈러 방정식 $E \times q \equiv p \pmod{(10^{9} + 7)}$를 만족해야 하며, $0$ 이상 $10^9+6$ 이하이어야 한다. 이 문제의 제한 조건에서는 그러한 수 $E$가 항상 존재하며 유일하게 결정됨을 보일 수 있다.

첫 번째 테스트 케이스에서 게임은 다음 두 가지 방식 중 하나로 진행될 수 있다(각 단계에서 제거되는 문자에는 밑줄이 그어져 있다).

• "ab" $\rightarrow$ "a" $\rightarrow$ "" (여기서 ""는 빈 문자열을 나타낸다). $a$와 ""는 모두 회문이므로 사탕 두 개를 먹게 된다.

• "ab" $\rightarrow$ "b" $\rightarrow$ "". $b$와 ""는 모두 회문이므로 사탕 두 개를 먹게 된다.

전체적으로 먹게 될 사탕 수의 기댓값은 $\frac{2 + 2}{2} = 2$개이다.

두 번째 테스트 케이스에서 게임은 다음 여섯 가지 방식 중 하나로 진행될 수 있다(각 단계에서 제거되는 문자에는 밑줄이 그어져 있다).

• "aba" $\rightarrow$ "ba" $\rightarrow$ "a" $\rightarrow$ ""

• "aba" $\rightarrow$ "ba" $\rightarrow$ "b" $\rightarrow$ ""

• "aba" $\rightarrow$ "aa" $\rightarrow$ "a" $\rightarrow$ ""

• "aba" $\rightarrow$ "aa" $\rightarrow$ "a" $\rightarrow$ ""

• "aba" $\rightarrow$ "ab" $\rightarrow$ "b" $\rightarrow$ ""

• "aba" $\rightarrow$ "ab" $\rightarrow$ "a" $\rightarrow$ ""

전체적으로 먹게 될 사탕 수의 기댓값은 $\frac{2 + 2 + 3 + 3 + 2 + 2}{6} = \frac{14}{6} = \frac{7}{3}$개이다. $333333338$은 출력 절에서 언급한 조건을 $333333338 \times 3 \equiv 7 \pmod{(10^{9} + 7)}$로서 만족하는 유일하게 결정된 수이므로, $333333338$이 이 테스트의 답이다.