Runs

#### World Finals, 2011

Submit Solution(Code Jam Page)

### Problem

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] ≠ b[i]`.

### Input

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.

### Output

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 ≤ T ≤ 100.
S is at least 1 character long.

#### Small dataset

S is at most 100 characters long.

#### Large dataset

S is at most 450000 characters long.
S has at most 100 runs.
The input file will not exceed 1 megabyte in size.

### Sample

 Input Output ``` 2 aabcd bookkeeper``` ``` Case #1: 24 Case #2: 7200```

Points Correct Attempted
14pt 11 12
16pt 10 11