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]\)
• \(1 \leq n \leq 5\cdot 10^5\)

Output

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

Example

aybabtu

103