Cho một xâu s chỉ gồm các chữ cái thường, độ dài n(1≤n≤106). Ta phải dùng đúng toàn bộ các ký tự của s để tạo một xâu mới; các ký tự bằng nhau không thể phân biệt.
Nhiệm vụ là đếm số xâu khác nhau có thể tạo được. In kết quả modulo 1000000007.
Input
Một dòng chứa xâu s.
Output
In kết quả theo yêu cầu, lấy modulo như đã nêu trong phần mô tả.
Constraints
1≤∣s∣≤106; s chỉ gồm chữ cái thường.
Scoring
Subtask 1 (50% số điểm): các test nhỏ trong 10 test đầu của bộ dữ liệu.
Subtask 2 (50% số điểm): không có giới hạn bổ sung.
Example
Test 1
Input
aab
Output
3
Giải thích: Trong aab, ký tự b có thể đứng ở một trong ba vị trí, nên có đúng ba xâu khác nhau.
Lời giải tóm tắt
Phân tích: Gọi c_x là số lần chữ cái x xuất hiện. Nếu tạm coi mọi bản sao là khác nhau, có n! thứ tự. Với một chữ có c_x bản sao, hoán đổi các bản sao ấy không làm xâu thay đổi, nên mỗi xâu phân biệt bị đếm c_x! lần. Các nhóm độc lập, vì vậy
Phân tích:ans = n! / (c_a! c_b! ... c_z!).
Phân tích: Modulo là số nguyên tố P = 10^9+7, nên phép chia cho c! được thay bằng nhân (c!)^(P-2) mod P. Ta tiền xử lý fact[i] = i! và invFact[i] = (i!)^{-1}. Chỉ cần một lần lũy thừa nhanh để tìm invFact[n], rồi dùng quan hệ invFact[i-1] = invFact[i] * i để đi lùi.
Phân tích: Các bước cài đặt: 1. Đếm 26 tần suất. 2. Tiền xử lý giai thừa/nghịch đảo đến n. 3. Khởi tạo ans = fact[n], nhân lần lượt invFact[c_x].
Thuật toán: Cài đặt trực tiếp công thức hoặc quy hoạch nêu trên, tiền xử lý các đại lượng tổ hợp cần thiết và chuẩn hóa mọi phép toán theo modulo của đề. Các trường hợp không khả thi được loại trước khi thực hiện phép chia modulo.
Chứng minh: Xét ánh xạ từ mọi hoán vị của n bản sao có nhãn sang xâu sau khi bỏ nhãn. Với mỗi xâu đích, ta có thể gán lại nhãn cho c_x vị trí của từng chữ theo c_x! cách; do đó mọi lớp tương đương có đúng ∏c_x! phần tử. Chia n! cho kích thước lớp cho đúng số lớp, tức số xâu khác nhau.