P16509 [GKS 2015 #B] Albocede DNA

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$ 个测试用例的输出。

### 限制 $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 完成