Sau khi giải trình tự bộ gen của đàn bò, Farmer John chuyển sang chỉnh sửa gen! Một bộ gen được biểu diễn bằng một xâu chỉ gồm các ký tự A, C, G và T. Độ dài tối đa của một bộ gen mà Farmer John xét là \(10^5\).

Farmer John bắt đầu với một bộ gen và chỉnh sửa nó theo các bước sau:

1. Tách bộ gen giữa mọi cặp ký tự liên tiếp giống nhau.
2. Đảo ngược từng xâu con thu được.
3. Ghép các xâu con đã đảo theo đúng thứ tự ban đầu.

Ví dụ, nếu FJ bắt đầu với bộ gen AGGCTTT, ông thực hiện:

AG | GCT | T | T
GA | TCG | T | T
GATCGTT

Không may, sau khi chỉnh sửa, máy tính của Farmer John gặp sự cố và ông mất trình tự bộ gen ban đầu. Hơn nữa, một số phần của bộ gen đã chỉnh sửa bị hỏng và được thay bằng dấu hỏi.

Cho trình tự của bộ gen đã chỉnh sửa, hãy giúp FJ xác định số bộ gen ban đầu có thể có, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng duy nhất chứa một xâu không rỗng, trong đó mỗi ký tự là A, G, C, T hoặc ?.

Dữ liệu ra

In số bộ gen ban đầu có thể có, lấy modulo \(10^9+7\).

Phân nhóm

• Trong các test 1-4, độ dài bộ gen không vượt quá \(10\).
• Trong các test 5-11, độ dài bộ gen không vượt quá \(10^2\).
• Trong các test 12-20, không có ràng buộc bổ sung.

Ví dụ

?

4

GAT?GTT

3

AGGATTT -> AG | GAT | T | T -> GA | TAG | T | T -> GATAGTT
TAGGTTT -> TAG | GT | T | T -> GAT | TG | T | T -> GATTGTT

Nguồn

USACO 2020 December Contest, Gold - Bovine Genetics: https://usaco.org/index.php?page=viewproblem2&cpid=1066

Tác giả: Benjamin Qi.