题目描述

Albocode 外星物种的 DNA 由 4 种核苷酸组成：a、b、c 和 d。不同的 Albocode 个体可能拥有不同的核苷酸序列，但任何 Albocode 的 DNA 序列都遵循以下所有规则：

• 它至少包含 a、b、c 和 d 各一份拷贝。
• 所有的 a 出现在所有 b 之前，所有的 b 出现在所有 c 之前，所有的 c 出现在所有 d 之前。
• 'a' 的数量与 'c' 的数量恰好相等。
• 'b' 的数量与 'd' 的数量恰好相等。

例如，abcd 和 aabbbccddd 是合法的 Albocode DNA 序列。acbd、abc 和 abbccd 则不是。

Albocode-n 是 Albocode 的一个进化物种。Albocode-n 的 DNA 序列由一个或多个合法的 Albocode DNA 序列首尾拼接而成。例如，abcd 和 aaabcccdaabbbccdddabcd 是合法的 Albocode-n DNA 序列。（注意，合法的 Albocode-n DNA 序列未必也是合法的 Albocode DNA 序列。）

在一次外星探险中，你找回了一段仅由 a、b、c 和 d 组成的有趣 DNA 序列。你想知道该序列的不同子序列中有多少是合法的 Albocode-n DNA 序列。（即使从原序列的不同位置选取核苷酸产生相同的合法子序列，它们仍被视为不同的子序列。）由于结果可能非常巨大，请将其对 $1000000007$（$10^9+7$）取模。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来的 $T$ 行每行包含一个仅由字符 a、b、c 和 d 组成的字符串 $S$。

输出格式

对于每个测试用例，输出一行包含 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是第 $x$ 个测试用例的输出。

5
abcd
aaaabcd
aaaabbccd
abcdabcdaabccd
b

Case #1: 1
Case #2: 4
Case #3: 28
Case #4: 71
Case #5: 0

提示

限制

$1 \le T \le 20$。

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

$1 \le \text{length of S} \le 50$。

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

$1 \le \text{length of S} \le 500$。

翻译由 DeepSeek V4 Pro 完成