런

소문자 알파벳 문자로 이루어진 문자열 S, 'a' - 'z'가 있다. 서로 같은 연속한 문자들로 이루어진 각각의 최대 길이 수열을 "run"이라고 한다. 예를 들어, "bookkeeper"에는 7개의 런이 있다. S와 런의 개수가 정확히 같은 S의 서로 다른 순열은 몇 개인가?

두 순열 a와 b는 서로 다른 문자를 갖는 인덱스 i가 하나라도 존재하는 경우 서로 다르다고 간주한다: a[i] ≠ b[i].

제한

1 ≤ T ≤ 100. S의 길이는 적어도 1자이다. 메모리 제한: 1GB.

작은 데이터셋 (테스트 세트 1 - 공개)

S의 길이는 최대 100자이다. 시간 제한: 30초.

큰 데이터셋 (테스트 세트 2 - 비공개)

S의 길이는 최대 450000자이다. S의 런 개수는 최대 100개이다. 입력 파일의 크기는 1메가바이트를 초과하지 않는다. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 관심 대상 문자열인 소문자 알파벳 문자로 이루어진 비어 있지 않은 문자열 S 하나가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 S와 런의 개수가 정확히 같은 S의 서로 다른 순열의 수를 1000003로 나눈 나머지이다.