런 (라지)

소문자 '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으로 나눈 나머지다.