Bovine Genetics

Farmer John chỉnh sửa bộ gen bò qua ba bước: (1) tách chuỗi tại vị trí giữa hai ký tự liên tiếp giống nhau, (2) đảo ngược mỗi chuỗi con, (3) nối lại. Bộ gen gốc đã bị mất, và bộ gen đã chỉnh sửa có một số vị trí bị hư hại (đánh dấu bằng ?). Xác định có bao nhiêu bộ gen gốc có thể tạo ra chuỗi đã chỉnh sửa.

Bộ gen gồm 4 loại nucleotide: A, G, C, T.

Dữ liệu vào

Một chuỗi không rỗng chứa các ký tự A, G, C, T hoặc ?.

Dữ liệu ra

Số bộ gen gốc có thể có, modulo ${10}^9+7$.

Ràng buộc

• Độ dài chuỗi $\le {10}^5$
• Test 1-4: độ dài $\le 10$
• Test 5-11: độ dài $\le 100$
• Test 12-20: không có ràng buộc thêm

Ví dụ