런 개수가 같은 순열

소문자 알파벳 a부터 z까지로 이루어진 문자열 $S$가 있다. 같은 문자가 연속으로 이어지는 극대 구간을 런이라고 부른다. 예를 들어 bookkeeper는 b, oo, kk, e, p, e, r로 나뉘므로 런이 7개다.

$S$의 순열 중에서 런의 개수가 $S$와 정확히 같은 것이 몇 개인지 구한다. 두 순열 $a$와 $b$는 어떤 위치 $i$에서 $a[i] \neq b[i]$이면 서로 다른 것으로 센다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 소문자 알파벳으로만 이루어진 빈 문자열이 아닌 문자열 $S$가 한 개씩 주어진다.

제한

• $1 \le T \le 100$
• $1 \le |S| \le 100$

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