Xâu ký tự ~X~ (khác rỗng) được gọi là xâu con của xâu ký tự ~Y~ nếu ta có thể xoá đi (hoặc không xóa) một số ký tự trong xâu ~Y~ để được xâu ~X~. Cho xâu kí tự ~S~ (chỉ gồm các kí tự chữ cái latin thường) có độ dài ~n~. Với mỗi xâu con ~C~ bất kì của xâu kí tự ~S~, gọi ~k~ là số cách xóa (hoặc không xóa) các kí tự trong ~S~ để thu được xâu con ~C~. Độ đẹp của xâu ~C~ được đánh giá bằng ~k^2~.

Ví dụ: ~S =~ 'aba', ta có thể tạo được các xâu con {'a'; 'b'; 'ab'; 'ba'; 'aa'; 'aba'}, với xâu con 'a' có 2 cách xóa: xóa 2 kí tự 'ab' của xâu ~S~; xóa 2 kí tự 'ba' của xâu ~S~, do đó độ đẹp của xâu này được đánh giá là 4. Tương tự cho các xâu {'b'; 'ab'; 'ba'; 'aa'; 'aba'}. Lúc này, tổng độ đẹp tất cả các xâu con của ~S~ bằng 9 (~4 + 1 + 1 + 1 + 1 + 1 = 9~).

Yêu cầu: Cho biết xâu ~S~, hãy tính tổng độ đẹp tất cả các xâu con của ~S~ (lấy phần dư khi chia kết quả cho ~10^9 + 7~).

Dữ liệu

Gồm 1 dòng chứa xâu kí tự ~S~ (chỉ gồm các kí tự chữ cái latin thường).

Kết quả

Gồm 1 dòng duy nhất chứa kết quả của bài toán (lấy phần dư khi chia kết quả cho ~10^9 + 7~).

Ví dụ

MSTRING.INP

aba

MSTRING.OUT

9

Giới hạn

• Có 40% số test ứng với 40% số điểm của bài có ~1 \le n \le 20~;
• Có 60% số test còn lại ứng với 60% số điểm của bài có ~1 \le n \le 2000~.