Cho xâu ~s~, nhiệm vụ của bạn là đếm số xâu khác nhau có thể tạo được bằng cách sắp xếp lại toàn bộ các kí tự của xâu ~s~.

Vì đáp án có thể rất lớn nên hãy chia dư cho ~10^9 + 7~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa xâu ~s~ có độ dài ~n~, chỉ gồm các chữ cái in thường từ a đến z.

Kết quả

In ra số xâu khác nhau có thể tạo được, đã chia dư cho ~10^9 + 7~.

Ví dụ

Đầu vào:

siu

Đầu ra:

6

Giải thích: Từ xâu siu ta tạo được ~6~ xâu khác nhau: siu, sui, isu, ius, uis, usi.

Giới hạn

• ~1 \le n \le 10^6~

Nếu mọi kí tự đôi một khác nhau thì có đúng ~n!~ cách sắp xếp. Khi một kí tự lặp lại ~c~ lần thì ~c!~ cách sắp xếp của riêng các bản sao đó cho cùng một xâu, nên phải chia đi. Gọi ~c_a, c_b, \ldots, c_z~ là số lần xuất hiện của từng chữ cái, đáp án là hệ số đa thức

~\dfrac{n!}{c_a! \cdot c_b! \cdot \ldots \cdot c_z!}~

Phép chia thực hiện bằng nghịch đảo modulo. Chú ý đáp án không phải ~n!~ chia cho số kí tự phân biệt — mà là chia cho tích các giai thừa của số lần xuất hiện.