P13382 [GCJ 2011 Finals] Runs

给定一个只包含小写字母 $a$ 到 $z$ 的字符串 $S$。每一段连续且相同的字符序列被称为一个“段”（run）。例如，字符串 "bookkeeper" 有 7 个段。请问有多少种不同的 $S$ 的排列方式，恰好拥有与 $S$ 相同数量的段？ 如果存在某个下标 $i$，使得排列 $a$ 和排列 $b$ 在该位置的字符不同（即 $a[i] \neq b[i]$），则认为这两个排列是不同的。

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

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

**限制条件** - $1 \leq T \leq 100$。 - $S$ 至少包含 $1$ 个字符。 **小数据范围（测试集 1 - 可见）** - $S$ 最多包含 $100$ 个字符。 - 时间限制：3 秒。 **大数据范围（测试集 2 - 隐藏）** - $S$ 最多包含 $450000$ 个字符。 - $S$ 最多包含 $100$ 个段。 - 输入文件大小不超过 1 MB。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译