Trong học kì này ở trường Hogwarts, Harry Potter tham gia lớp học “Muggle học”, trong lớp học này Harry Potter được học về bộ môn lập trình mà được rất nhiều Muggle yêu thích. Hôm nay Harry Potter được giáo sư dạy về thuật toán quy hoạch động, Harry cảm thấy rất hứng thú với bài toán xâu đối xứng, một bài toán kinh điển về quy hoạch động. Bài toán được nói lại như sau: Cho một xâu ~s~ có độ dài là ~n~, hãy đếm xem có bao nhiêu xâu con (không nhất thiết phải liên tiếp) của ~s~ mà theo thứ tự là xâu đối xứng.

Nhưng Harry nghĩ ra một bài toán khác là cho xâu ~s~, với mỗi xâu bất kì, gọi ~x~ là số cách để tạo ra xâu đó bằng cách xóa một số (hoặc không) kí tự trong xâu ~s~, độ đẹp của xâu đó là ~x^2~, không tính xâu rỗng. Harry muốn tìm tổng độ đẹp của tất cả các xâu khác nhau có thể tạo được bằng cách xóa một số (hoặc không) kí tự trong xâu ~s~.

Yêu cầu: Cho biết xâu ~s~, tính tổng độ đẹp của các xâu khác nhau có thể tạo được từ xâu ~s~ lấy dư cho ~10^9 + 7~.

Input

• Dòng đầu chứa xâu ~s~ gồm các kí tự in thường từ ‘a’ đến ‘z’.

Output

• Một dòng duy nhất là kết quả của bài toán lấy dư với ~10^9 + 7~.

Sample Input 1

banana

Sample Output 1

139