P16880 [GKS 2022 #C] Palindromic Deletions

最近，与单词和字符串相关的游戏非常流行。现在 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$ 种可能的过程（每一步删除的字符用下划线标出）： 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 完成