Cho xâu ~S~ chỉ gồm các chữ cái in hoa trong bảng chữ cái tiếng Anh. Gọi ~N=|S|~; các ký tự của ~S~ được đánh số từ ~1~ đến ~N~.

Bạn chọn một dãy chỉ số không rỗng:

$$1 \le i_1 < i_2 < \cdots < i_K \le N$$

và tạo xâu ~T=S_{i_1}S_{i_2}\cdots S_{i_K}~.

Xâu ~T~ được gọi là luân phiên nếu các ký tự liên tiếp lần lượt tăng, giảm, tăng, giảm, ... theo thứ tự trong bảng chữ cái, nghĩa là:

$$T_1 < T_2> T_3 < T_4 > T_5 < \cdots$$

Xâu gồm một ký tự cũng được xem là luân phiên.

Hãy đếm số dãy chỉ số có thể chọn để tạo thành một xâu luân phiên. Hai cách chọn được xem là khác nhau nếu dãy chỉ số được chọn khác nhau, kể cả khi hai xâu tạo thành giống nhau.

Trong bài toán này, A < B < ... < Z.

Dữ liệu vào

• Dòng duy nhất chứa xâu ~S~ (~1\le |S|\le10^6~), chỉ gồm các chữ cái in hoa từ A đến Z.

Dữ liệu ra

In ra số cách chọn, lấy phần dư khi chia cho ~10^9+7~.

Ví dụ

Input

ACBCD

Output

16

Giải thích

Theo độ dài ~1,2,3,4~, số cách chọn lần lượt là ~5,8,1,2~. Các xâu tương ứng có độ dài từ ~2~ trở lên là:

• Độ dài ~2~: AC, AB, AC, AD, CD, BC, BD, CD.
• Độ dài ~3~: ACB.
• Độ dài ~4~: ACBC và ACBD.

Hai lần xuất hiện của AC và CD ở trên đến từ các vị trí khác nhau trong ~S~, vì vậy được tính là các cách chọn khác nhau.

Ràng buộc

• Subtask 1 (20%): ~|S|\le20~.
• Subtask 2 (30%): ~|S|\le2000~.
• Subtask 3 (50%): Không có ràng buộc nào thêm.