시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 97 43 14 29.787%

문제

DNA 문자열은 뉴클레오티드 (A, C, G, T)의 연속이다. 어떤 DNA 문자열은 단백질로 바꿀 수 있는데, 이것은 길이가 0이 아닌 아미노산의 연속이다. DNA 변환 과정을 살펴보자.

  1. 왼쪽부터 차례대로 3개씩 뉴클레오티드를 겹치지 자른다.이 3쌍은 코돈이라고 한다. 어쩌면, 마지막에 한 개 또는 두 개의 뉴클레오티드가 남을 수도 있는데, 이런 경우에는 무시하면 된다. 만약 DNA 문자열이 ACCTGTACG 였다면, 다음과 같은 코돈이 순서대로 나온다. ACC, TGT, ACG가 나오고, DNA 문자열이 ACCTGTAC였다면, ACC, TGT와 같은 코돈이 순서대로 나온다. (마지막에 남는 AC는 무시해도 됨)
  2. 코돈 변환 표가 주어진다. 이제 왼쪽부터 차례대로 코돈 변환 표에서 그 코돈을 찾아서 대응하는 아미노산으로 바꾸면 된다. 만약 대응하는 것이 없다면, 단백질로 변환되지 못한다. 예를 들어, ACC가 thr에 대응하고, TGT가 cys에 대응하고, ACG가 thr에 대응한다면, DNA 문자열 ACCTGTACG는 thr cys thr로 변환될 것이다.

가끔 DNA 문자열 중 하나 또는 그 이상의 뉴클레오티드가 사라지기도 한다. 이러한 현상을 결실이라고 한다. DNA 문자열이 ACTG 이었고, 결실이 일어난다면, ACG, CG와 같이 될 것이다. (2개는 하나의 예이다)

DNA 문자열과 코돈 변환 표가 주어졌을 때, 결실이 0개 또는 그 이상 일어났을 때, 나올 수 있는 서로 다른 단백질이 몇 개 인지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 DNA 문자열이 주어진다. 길이는 최대 2,600이다. 둘째 줄에는 코돈 변환 표에 들어있는 코돈의 개수 M이 주어지고, 이 수는 50보다 작거나 같다. 셋째 줄부터 M개의 줄에는 코돈 변환 표가 주어지는데, 각각은 "코돈 아미노산"과 같이 생겼다. 코돈은 A, C, G, T로만 이루어진 길이가 3인 문자열이고, 아미노산은 알파벳 소문자 또는 대문자로 이루어진 길이가 최대 20인 비어있지 않은 문자열이다. 코돈 변환 표는 중복되지 않는다.

출력

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

예제 입력

ACTG
4
ACT gua
ACG sys
ATG leu
CTG thr

예제 출력

4

힌트

gua : 결실이 일어나지 않거나, G가 결실 되었을 때 cys : T가 결실되었을 때 leu : C가 결실되었을 때 thr : A가 결실되었을 때

출처