Tôi có một chuỗi \(S\) bao gồm các ký tự chữ cái viết thường từ 'a' đến 'z'. Mỗi dãy ký tự giống nhau liên tiếp dài nhất được gọi là một "run" (đoạn chạy). Ví dụ, chuỗi "bookkeeper" có 7 runs. Có bao nhiêu hoán vị khác nhau của \(S\) có đúng số lượng runs bằng với số lượng runs của \(S\)?

Hai hoán vị \(a\) và \(b\) được coi là khác nhau nếu tồn tại một vị trí \(i\) mà tại đó chúng có ký tự khác nhau: \(a[i] \neq b[i]\).

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ dữ liệu, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa một chuỗi duy nhất \(S\) gồm các ký tự chữ cái viết thường và không rỗng.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ dữ liệu (bắt đầu từ 1) và y là số lượng hoán vị khác nhau của \(S\) có đúng số lượng runs bằng với \(S\), lấy modulo \(1000003\).

Ràng buộc

• \(1 \le T \le 100\).
• \(S\) có độ dài ít nhất 1 ký tự.

Phân nhóm

• Test set 1 (Visible): \(S\) có độ dài tối đa 100 ký tự.
• Test set 2 (Hidden): \(S\) có độ dài tối đa \(450,000\) ký tự. \(S\) có tối đa 100 runs. Kích thước tệp đầu vào không quá 1 megabyte.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
aabcd
bookkeeper

Case #1: 24
Case #2: 7200

Nguồn

Google Code Jam 2011, Chung kết thế giới, bài Runs.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.