Điều chỉnh bộ gen

Nông dân John là người nhận được chứng nhận nhà nông số 1 tại đất nước Mỹ với dự án giải trình tự bộ gen của những con bò với mục đích quản lý sức khỏe, khả năng sinh sản, khả năng cung cấp thịt, sữa của chúng. Sau khi được trao danh hiệu cao quý và đầy tự tạo, anh ấy quyết định thực hiện một dự án mới là chỉnh sửa bộ gen của các con bò để thế hệ của những con bò sẽ mang nhiều bộ gen trội nhằm phát triển nền chăn nuôi bò của quốc gia. Bộ gen anh ấy đang nghiên cứu được mô tả bằng một chuỗi chỉ gồm 4 loại kí tự A, C, T, G và có chiều dài tối đa là \(10^5\). Nông dân John có một bộ gen ban đầu và anh ấy tiến hành chỉnh sửa như sau:

• Tách bộ gen thành các chuỗi con ở các vị trí có hai kí tự liên tiếp giống nhau.
• Đảo ngược từng chuỗi con.
• Nối lại các chuỗi con đã đảo ngược theo cùng thứ tự.

Ví dụ với bộ gen ban đầu là AGGCTTT thì anh ấy thực hiện các bước sau:

• Tách bộ gen thành: AG | GCT | T | T.
• Đảo ngược các chuỗi con: GA | TCG | T | T.
• Nối các chuỗi con: GATCGTT.

Thật không may, sau khi chỉnh sửa bộ gen thì nông dân John để mất trình tự của bộ gen và một số vị trí bị mất, các vị trí bị mất này được thay thế bằng dấu chấm hỏi.

Yêu cầu: Từ bộ gen đã chỉnh sửa hãy giúp nông dân John tính số khả năng xảy ra của bộ gen ban đầu.

Input

• Một dòng duy nhất chứa chuỗi gồm các kí tư A, C, T, G và dấu chấm hỏi.

Output

• Ghi ra một số là phần dư của số khả năng xảy ra của bộ gen ban đầu trong phép chia cho \(10^9+7\).

Example

?

4

GAT?GTT

3

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Độ dài bộ gen ban đầu không vượt quá \(10\).

• Subtask \(2\) (\(40\%\) số điểm): Độ dài bộ gen ban đầu không vượt quá \(10^2\).

• Subtask \(3\) (\(40\%\) số điểm): Không có giới hạn gì thêm.