Cho một xâu \(S\) chỉ chứa hai kí tự a và b. Bạn có thể thực hiện các thao tác sau nhiều lần tùy ý hoặc không cần thao tác:

• Chọn một lần chuỗi con aa ở vị trí bất kì mà nó xuất hiện trong xâu \(S\) và thay nó bằng b.
• Chọn một lần chuỗi con bb ở vị trí bất kì mà nó xuất hiện trong xâu \(S\) và thay nó bằng a.

Yêu cầu: Bạn hãy đếm xem có bao nhiêu xâu con khác nhau có thể tạo ra với các thao tác trên.

Input

• Chứa một xâu \(S\) duy nhất (độ dài của xâu \(S\) không quá \(2 \times 10^7\)).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Độ dài của xâu không quá \(10^5\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

aaaa

6

aabb

5

ababababa

1

babbabaaba

35