Description

给定一个只包含小写字母 $a$ 到 $z$ 的字符串 $S$。每一段连续且相同的字符序列被称为一个“段”（run）。例如，字符串 "bookkeeper" 有 7 个段。请问有多少种不同的 $S$ 的排列方式，恰好拥有与 $S$ 相同数量的段？

如果存在某个下标 $i$，使得排列 $a$ 和排列 $b$ 在该位置的字符不同（即 $a[i] \neq b[i]$），则认为这两个排列是不同的。

Input Format

第一行输入一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行包含一个非空的小写字母字符串 $S$，即待处理的字符串。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示恰好有与 $S$ 相同数量段的不同排列数，对 $1000003$ 取模。

2
aabcd
bookkeeper

Case #1: 24
Case #2: 7200

Hint

限制条件

• $1 \leq T \leq 100$。
• $S$ 至少包含 $1$ 个字符。

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

• $S$ 最多包含 $100$ 个字符。
• 时间限制：3 秒。

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

• $S$ 最多包含 $450000$ 个字符。
• $S$ 最多包含 $100$ 个段。
• 输入文件大小不超过 1 MB。
• 时间限制：6 秒。

由 ChatGPT 4.1 翻译