|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||4||4||4||100.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?
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.
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