题目描述

最近，与单词和字符串相关的游戏非常流行。现在 Edsger 试图创建一款类似的新游戏。以下是他的初步构想。

Edsger 的新游戏名为“回文删除”。作为游戏玩家，你将获得一个长度为 $N$ 的字符串。然后你将执行以下过程 $N$ 次：

1. 在当前字符串中均匀随机地选择一个下标。
2. 删除该下标处的字符。你将得到一个新字符串，长度减少 $1$。
3. 如果新字符串是回文，你将获得一块糖果作为庆祝。

现在 Edsger 想知道：给定初始字符串，在整个游戏过程中你期望获得的糖果数量是多少？

输入格式

输入的第一行给出测试用例的数量 $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 \le E \le 10^9 + 6$。可以证明，在本问题的限制下，这样的 $E$ 总是存在且唯一确定。

2
2
ab
3
aba

Case #1: 2
Case #2: 333333338

提示

在第一个测试用例中，游戏有 $2$ 种可能的过程（每一步删除的字符用下划线标出）：

1. "$a\underline{b}$" $\to$ "$a$" $\to$ ""（其中 "" 表示空字符串）。这里 "$a$" 和 "" 都是回文，因此你将获得 $2$ 块糖果。
2. "$\underline{a}b$" $\to$ "$b$" $\to$ ""。这里 "$b$" 和 "" 都是回文，因此你将获得 $2$ 块糖果。

因此，期望获得的糖果数为 $\frac{2+2}{2}=2$。

在第二个测试用例中，游戏有 $6$ 种可能的过程（每一步删除的字符用下划线标出）：

1. "$\underline{a}ba$" $\to$ "$\underline{b}a$" $\to$ "$\underline{a}$" $\to$ ""
2. "$\underline{a}ba$" $\to$ "$b\underline{a}$" $\to$ "$\underline{b}$" $\to$ ""
3. "$a\underline{b}a$" $\to$ "$\underline{a}a$" $\to$ "$\underline{a}$" $\to$ ""
4. "$a\underline{b}a$" $\to$ "$a\underline{a}$" $\to$ "$\underline{a}$" $\to$ ""
5. "$ab\underline{a}$" $\to$ "$\underline{a}b$" $\to$ "$\underline{b}$" $\to$ ""
6. "$ab\underline{a}$" $\to$ "$a\underline{b}$" $\to$ "$\underline{a}$" $\to$ ""

因此，期望获得的糖果数为 $\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$ 是该测试用例的答案。

限制条件

$1 \le T \le 20$。

字符串 $S$ 仅由小写英文字母组成。

测试集 1

$2 \le N \le 8$。

测试集 2

$2 \le N \le 400$。

翻译由 DeepSeek V4 Pro 完成