시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB57917312135.588%

문제

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

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

가끔 DNA 문자열 중 하나 이상의 뉴클레오타이드가 사라지기도 한다. 이러한 현상을 결실이라고 한다. 예를 들어, DNA 문자열이 ACTG인데 결실이 일어난다면 ACG나 CG 등이 될 수 있다.

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

입력

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

출력

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

예제 입력 1

ACTG
4
ACT gua
ACG sys
ATG leu
CTG thr

예제 출력 1

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

예제 입력 2

AAACCC
2
AAA thr
CCC cys

예제 출력 2

3

예제 입력 3

AAATCCC
4
AAA gua
TCC dop
AAT dop
CCC gua

예제 출력 3

5

출처