회문 삭제

Edsger가 새로 만든 게임 Palindromic Deletions에서는 길이가 $N$인 문자열 하나가 주어진다. 이후 아래 과정을 $N$번 수행한다.

1. 현재 문자열에서 인덱스 하나를 균등한 확률로 무작위로 고른다.
2. 그 인덱스의 문자를 삭제한다. 그러면 길이가 1 줄어든 새 문자열이 된다.
3. 새 문자열이 회문이면 사탕을 하나 먹는다.

시작 문자열이 주어졌을 때, 게임 동안 먹는 사탕 개수의 기댓값을 구한다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 이후 $T$개의 테스트 케이스가 나오며, 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 문자열의 길이 $N$이 주어지고, 둘째 줄에는 길이가 $N$인 소문자 영문자 문자열 $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$는 항상 존재하고 하나로 정해진다.

• $1 \le T \le 20$.
• $S$는 영문 소문자로만 이루어진다.

시간 제한은 30000ms, 메모리 제한은 1024MB이다.