Cho một xâu ký tự chỉ gồm chữ cái in thường. Đếm số hoán vị phân biệt của xâu. Kết quả modulo \(10^9+7\).

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).

Định dạng đầu ra

• Một số nguyên là số hoán vị phân biệt modulo \(10^9+7\).

Ví dụ

Input:

aab

Output:

3

Giải thích: Các hoán vị: aab, aba, baa.

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).