题目描述

I have a string $S$ consisting of lower-case alphabetic characters, 'a' - 'z'. Each maximal sequence of contiguous characters that are the same is called a "run". For example, "bookkeeper" has 7 runs. How many different permutations of $S$ have exactly the same number of runs as $S$?

Two permutations $a$ and $b$ are considered different if there exists some index $i$ at which they have a different character: $a[i] \neq b[i]$.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ lines follow. Each contains a single non-empty string of lower-case alphabetic characters, $S$, the string of interest.

输出格式

For each test case, output one line containing "Case #$x$: $y$", where $x$ is the case number (starting from 1) and $y$ is the number of different permutations of $S$ that have exactly the same number of runs as $S$, modulo $1000003$.

2
aabcd
bookkeeper

Case #1: 24
Case #2: 7200

提示

Limits

• $1 \leq T \leq 100$.
• $S$ is at least $1$ character long.

Small dataset (Test set 1 - Visible)

• $S$ is at most $100$ characters long.
• Time limit: 30 3 seconds.

Large dataset (Test set 2 - Hidden)

• $S$ is at most $450000$ characters long.
• $S$ has at most $100$ runs.
• The input file will not exceed $1$ megabyte in size.
• Time limit: 60 6 seconds.