P16518 [GKS 2015 #E] Lazy Spelling Bee

在懒惰拼字比赛中，参赛者会收到一个需要拼写的目标单词 $W$。如果参赛者给出的答案单词 $A$ 长度与目标单词相同，并且对于 $A$ 长度范围内的每一个 $i$，$A$ 的第 $i$ 个字母要么是 $W$ 的第 $i$ 个、第 $(i-1)$ 个或第 $(i+1)$ 个字母，那么 $A$ 就是可接受的。（$A$ 的第一个字母必须匹配 $W$ 的第一个或第二个字母，因为 $W$ 的第 $0$ 个字母不存在。类似地，$A$ 的最后一个字母必须匹配 $W$ 的最后一个或倒数第二个字母。）注意，目标单词本身始终是一个可接受的答案单词。 你正在筹办一场懒惰拼字比赛，并被要求对于每个目标单词，求出共有多少个不同的可接受答案单词。由于这个数字可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模的结果。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例，每个用例占一行，包含一个仅由小写英文字母（a 到 z）组成的字符串。

对于每个测试用例，输出一行形如 `Case #x: y` 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是不同的可接受答案单词的数量对 $10^9 + 7$ 取模的结果。

在样例用例 #1 中，可接受的答案单词有 aa、ag、ga 和 gg。 在样例用例 #2 中，唯一可接受的答案单词是 aa。 ### 限制 - $1 \le T \le 100$。 - 每个字符串的长度 $\ge 1$。 **小数据集（测试集 1 - 可见）** - 每个字符串的长度 $\le 5$。 **大数据集（测试集 2 - 隐藏）** - 每个字符串的长度 $\le 1000$。 翻译由 DeepSeek V4 Pro 完成