Xét xâu \(S\) là một xâu chỉ gồm các kí tự in hoa. Một xâu con của xâu \(S\) là xâu thu được khi xoá một số kí tự (hoặc có thể là không xóa kí tự nào) khỏi xâu \(S\) và giữ nguyên thứ tự các kí tự còn lại. Ví dụ, xâu ABC có các xâu con là A, AC, BC, ABC nhưng BA hay CAB không phải là xâu con của xâu ABC. Dễ thấy, xâu \(S\) độ dài \(N\) sẽ có \(2^N - 1\) xâu con không rỗng.

Để đánh giá độ lặp lại của các xâu con này, Hồng định nghĩa hàm \(f\):

trong đó \(w(S)\) là tập các xâu con khác rỗng của \(S\), \(r(s)\) là số lần lặp của \(s\), \(|s|\) là độ dài xâu \(s\).

Ví dụ xét $S = $ ABAB, các xâu con của \(S\) bao gồm A (2 lần), B (2 lần), AB (3 lần) và AA, BB, BA, AAB, ABB, ABA, BAB, ABAB mỗi xâu xuất hiện 1 lần. Khi đó:

Yêu cầu: Cho xâu \(S\), hãy tính \(f(S)\). Vì \(f(S)\) có thể rất lớn, Hồng cần đưa ra \(f(S) \pmod{10^9 + 7}\), trong đó \(\%\) là phép chia lấy dư.

Input

• Gồm một dòng chứa xâu \(S\) chỉ gồm kí tự in hoa có độ dài không quá \(200\).

Output

• Ghi ra một dòng chứa một số nguyên là giá trị \(f(S) \pmod{10^9 + 7}\).

Example

ABAB

48

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài thỏa mãn: \(|S| \le 20\).
• Có \(15\%\) số test khác ứng với \(15\%\) số điểm của bài thỏa mãn: \(S\) gồm các kí tự giống nhau.
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(s_i \le s_j\) nếu \(i < j\).
• Có \(35\%\) số test còn lại ứng với \(35\%\) số điểm của bài thỏa mãn: \(|S| \le 200\).