런 (라지)

S의 문자를 재배열해 최대 동일 문자 구간 개수가 S와 같은 서로 다른 문자열 개수를 1000003으로 나눈 나머지를 구합니다.

어려움8조합론동적 계획법아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제3

문제

소문자 'a'부터 'z'까지로만 이루어진 문자열 $S$ 가 있다. 같은 문자가 연속으로 이어지는 최대 구간을 런(run)이라고 부른다. 예를 들어 "bookkeeper"의 런은 7개다. $S$ 를 재배열해서 얻을 수 있는 서로 다른 문자열 중에서, 런의 개수가 $S$ 와 똑같은 것은 몇 개인가?

두 재배열 $a$ 와 $b$ 는 어떤 위치 $i$ 에서 $a[i] \ne b[i]$ 이면 서로 다르다고 본다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 다음 $T$ 개의 줄에는 소문자로만 이루어진 비어 있지 않은 문자열 $S$ 가 한 줄에 하나씩 주어진다.

제한

$1 \le T \le 100$
$S$ 의 길이는 1 이상 450000 이하다.
$S$ 의 런은 100개 이하다.
입력 파일의 크기는 1메가바이트를 넘지 않는다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 런의 개수가 $S$ 와 같은 서로 다른 재배열의 개수를 1000003으로 나눈 나머지다.