Nhập vào xâu ký tự \(S\). Hãy đếm xem có bao nhiêu xâu khác nhau có thể tạo ra bằng cách hoán vị các xâu con của \(S\) (các xâu con không cần là xâu chứa ký tự liên tiếp). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Input

• Gồm một dòng chứa xâu ký tự \(S\).

Output

• In ra số dư của kết quả khi cho cho \(10^9+7\).

Ví dụ

Sample input 1

abb

Sample output 1

8

Có \(8\) xâu khác nhau có thể được tạo ra là: a, b, ab, ba, bb, abb, bab, bba.

Sample input 2

haii

Sample output 2

34

Sample input 3

qwertyuiopasdfghjklzxcvbnm

Sample output 3

466719859

Ràng buộc

• \(1\leq |S|\leq5000\).