Cho trước một xâu. Bạn có thể xóa một lượng tùy ý các kí tự trong nó, nhưng không thể thay đổi thứ tự của những kí tự còn lại.

Hỏi bạn có thể tạo ra được bao nhiêu xâu khác nhau?

Input

Dòng duy nhất chứa một xâu độ dài \(n\). Mỗi kí tự đều thuộc đoạn \([a-z]\).

Output

In ra một số nguyên là số lượng xâu theo modulo \(10^9 + 7\).

Constraints

• $ 1≤n≤5⋅10^5 $

Example

Sample input

aybabtu

103