시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 4 3 3 75.000%

## 문제

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

## 입력

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.

### Limits

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

## 출력

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.

## 예제 입력 1

2
aabcd
bookkeeper


## 예제 출력 1

Case #1: 24
Case #2: 7200


## 채점 및 기타 정보

• 예제는 채점하지 않는다.