Bovine Genetics

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 $\leq 10^{5}$
Test 1-4: độ dài $\leq 10$
Test 5-11: độ dài $\leq 100$
Test 12-20: không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
?	4	Ký tự `?` có thể là bất kỳ nucleotide nào trong 4 loại.
GAT?GTT	3	Có 3 bộ gen gốc hợp lệ: AGGCTTT, AGGATTT, TAGGTTT.

Bình luận

Không có bình luận tại thời điểm này.