P13382 [GCJ 2011 Finals] Runs

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$.

**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.