DNA 결실과 단백질 개수

DNA 문자열은 뉴클레오타이드 A, C, G, T로 이루어진 문자열이다. 어떤 DNA 문자열은 길이가 1 이상인 아미노산 수열, 즉 단백질로 변환될 수 있다. 변환 과정은 다음과 같다.

1. 문자열을 왼쪽부터 겹치지 않게 3글자씩 자른다. 이렇게 만든 각 조각을 코돈이라고 한다. 끝에 뉴클레오타이드가 1개 또는 2개 남으면 무시한다. 예를 들어 DNA 문자열이 ACCTGTACG이면 코돈은 ACC, TGT, ACG 순서로 만들어지고, ACCTGTAC이면 ACC, TGT만 만들어지며 마지막 AC는 무시된다.
2. 주어진 코돈 변환 표에서 각 코돈에 대응하는 아미노산을 찾아 왼쪽부터 차례대로 바꾼다. 어떤 코돈이 표에 없으면 그 문자열은 단백질로 변환될 수 없다. 예를 들어 ACC가 thr, TGT가 cys, ACG가 thr에 대응한다면 ACCTGTACG는 thr cys thr로 변환된다.

결실은 DNA 문자열에서 하나 이상의 뉴클레오타이드가 삭제되는 현상이다. 삭제되지 않은 뉴클레오타이드들의 상대적인 순서는 그대로 유지된다. 예를 들어 ACTG에서 결실이 일어나면 ACG나 CG 등이 될 수 있다.

DNA 문자열과 코돈 변환 표가 주어진다. 결실을 0번 이상 적용했을 때 만들 수 있는 서로 다른 단백질의 개수를 구하시오.

첫째 줄에 DNA 문자열이 주어진다. 문자열의 길이는 최대 2,500이다.

둘째 줄에 코돈 변환 표에 있는 코돈의 개수 M이 주어진다. M은 50 이하이다.

셋째 줄부터 M개의 줄에 코돈 변환 표가 주어진다. 각 줄에는 코돈과 아미노산이 이 순서로 주어진다. 코돈은 A, C, G, T로만 이루어진 길이 3의 문자열이다. 아미노산은 알파벳 대문자 또는 소문자로 이루어진 길이 1 이상 20 이하의 문자열이다. 같은 코돈은 변환 표에 두 번 이상 주어지지 않는다.

첫째 줄에 만들 수 있는 서로 다른 단백질의 개수를 1,000,000,007로 나눈 나머지를 출력한다.