Xâu là một dãy ký tự trong bộ mã ASCII. Số lượng ký tự trong một xâu gọi là độ dài của xâu.

Một xâu được gọi là xâu con của xâu \(S\) nếu là xâu nhận được từ \(S\) bằng cách bỏ đi một số ký tự của \(S\) và giữ nguyên thứ tự của các ký tự còn lại. Ví dụ: xâu A, AC, ACD, ABCD là các xâu con của xâu ABCD. Xâu AA là xâu con của xâu AAA khi bỏ ký tự thứ ba, xâu AA cũng là xâu con của xâu AAA khi bỏ ký tự thứ hai.

Một xâu được gọi là xâu luân phiên nếu nó chỉ gồm các chữ cái Latin in hoa và theo thứ tự các chữ cái đó trong bộ mã ASCII thì chữ cái thứ nhất nhỏ hơn chữ cái thứ hai, chữ cái thứ hai lớn hơn chữ cái thứ ba, chữ cái thứ ba nhỏ hơn chữ cái thứ tư,... Xâu chỉ gồm một chữ cái Latin in hoa cũng là một xâu luân phiên.

Yêu cầu: Cho xâu \(S\) chỉ gồm các chữ cái Latin in hoa, hãy xác định xâu \(S\) có bao nhiêu xâu con luân phiên?

Input

• Gồm một dòng duy nhất chứa xâu \(S\).

Output

• In ra một số nguyên dương là phần dư của kết quả tìm được khi chia cho \(10^9+7\).

Ví dụ

Sample input

ACB

Sample output

6

Note

Xâu ACB có \(7\) xâu con khác rỗng: A, C, B, AC, AB, CB, ACB; chỉ xâu CB không phải là xâu luân phiên (\(C>B\)), tất cả các xâu còn lại đều là xâu luân phiên.

Ràng buộc

Ký hiệu: \(|S|\) là độ dài của xâu \(S\).

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài có \(|S|\leq20\);
• Có \(40\%\) số test khác ứng với \(40\%\) số điểm của bài có \(|S|\leq1000\);
• Có \(30\%\) số test khác ứng với \(30\%\) số điểm còn lại của bài có \(|S|\leq1000000\);