소 유전학

소들의 게놈을 시퀀싱한 뒤, 농부 존은 이제 게놈 편집에 도전하고 있다! 알다시피 게놈은 A, C, G, T로 이루어진 문자열로 나타낼 수 있다. 농부 존이 고려하는 게놈의 최대 길이는 \(10^5\)이다.

농부 존은 게놈 하나로 시작하여 다음 단계를 수행해 편집한다.

1. 연속한 두 개의 같은 문자 사이마다 게놈을 나눈다.
2. 나뉜 각 부분 문자열을 뒤집는다.
3. 뒤집힌 부분 문자열들을 같은 순서로 이어 붙인다.

예를 들어 농부 존이 게놈 AGGCTTT로 시작했다면 다음 단계를 수행한다.

1. 연속한 G 사이와 T 사이에서 나누어 AG | GCT | T | T를 얻는다.
2. 각 부분 문자열을 뒤집어 GA | TCG | T | T를 얻는다.
3. 부분 문자열들을 이어 붙여 GATCGTT를 얻는다.

안타깝게도 게놈을 편집한 후 농부 존의 컴퓨터가 고장 나서 처음 시작했던 게놈의 서열을 잃어버렸다. 게다가 편집된 게놈의 일부가 손상되어 물음표로 대체되어 있다.

편집된 게놈의 서열이 주어질 때, 원래 게놈으로 가능한 경우의 수를 \(10^9+7\)로 나눈 나머지를 구해 농부 존을 도와주자.

문제 제공: Benjamin Qi

배점

• 테스트 케이스 1-4에서는 게놈의 길이가 최대 \(10\)이다.
• 테스트 케이스 5-11에서는 게놈의 길이가 최대 \(10^2\)이다.
• 테스트 케이스 12-20에서는 추가 제약이 없다.

문제 제공: Benjamin Qi

각 문자가 A, G, C, T, ? 중 하나인, 비어 있지 않은 문자열이 주어진다.

가능한 원래 게놈의 개수를 \(10^9+7\)로 나눈 나머지를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > December > Gold