题目描述

在懒惰拼字比赛中，参赛者会收到一个需要拼写的目标单词 $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$ 取模的结果。

4
ag
aa
abcde
x

Case #1: 4
Case #2: 1
Case #3: 108
Case #4: 1

提示

在样例用例 #1 中，可接受的答案单词有 aa、ag、ga 和 gg。

在样例用例 #2 中，唯一可接受的答案单词是 aa。

限制

• $1 \le T \le 100$。
• 每个字符串的长度 $\ge 1$。

小数据集（测试集 1 - 可见）

• 每个字符串的长度 $\le 5$。

大数据集（测试集 2 - 隐藏）

• 每个字符串的长度 $\le 1000$。

翻译由 DeepSeek V4 Pro 完成