DNA

시간 제한2초메모리 제한512 MB

요약

DNA 문자 A, T, G, C에 대한 문맥 자유 문법과 각 문자별 목표 개수가 주어질 때, 그 개수에 맞게 문법이 생성하는 문자열의 수를 1e9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 수학, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

유전자는 A, T, G, C로 이루어진 문자열이다. 이 세계의 유전자는 이상하게도 특정 문법 규칙을 따른다고 알려져 있다.

문법 규칙은 다음과 같은 형태로 주어진다.

비종단기호1: 기호1_1 기호1_2 ... 기호1_n1
비종단기호2: 기호2_1 기호2_2 ... 기호2_n2
...
비종단기호m: 기호m_1 기호m_2 ... 기호m_nm

기호는 비종단기호 또는 종단기호 중 하나이다. 비종단기호는 소문자 문자열로 표현되고, 종단기호는 A, T, G, C 중 일부 문자가 "["와 "]"로 둘러싸인 문자열로 표현된다.

문법 규칙의 예는 다음과 같다.

dna: a a b b
a: [AT]
b: [GC]

"비종단기호i: 기호i_1 기호i_2 ... 기호i_ni"를 비종단기호 i의 규칙이라 하고, 규칙은 문법 규칙에 나타나는 각 비종단기호마다 정확히 하나씩 존재한다.

문자열 s가 비종단기호 i에 "매치한다"는 것은, s = s1 + s2 + ... + sni가 되는 s의 부분 문자열 {sj}가 존재하고, sj (1 ≤ j ≤ ni)가 규칙 안의 기호 j에 매치하는 것을 말한다.

문자열 s가 종단기호에 "매치한다"는 것은, 문자열이 1글자로 이루어지고 그 문자가 종단기호를 나타내는 문자열에 포함되는 것을 말한다.

문자열이 문법 규칙을 따른다는 것은, 비종단기호 1에 그 문자열이 매치한다는 것이다.

규칙 i는 기호 중에 비종단기호 j (j ≤ i)를 포함하지 않는다.

문법 규칙과 4개의 정수 Na, Nt, Ng, Nc가 주어진다. 문법 규칙을 따르고, A를 정확히 Na개, T를 정확히 Nt개, G를 정확히 Ng개, C를 정확히 Nc개 포함하는 유전자의 총수를 1,000,000,007로 나눈 나머지를 구하시오.

입력

Na Nt Ng Nc
m
비종단기호1: 기호11 기호12 ... 기호1n1
비종단기호2: 기호21 기호22 ... 기호2n2
...
비종단기호m: 기호m1 기호m2 ... 기호mnm

0 ≤ Na, Nt, Ng, Nc ≤ 50
1 ≤ m ≤ 50
1 ≤ ni ≤ 10
1 ≤ 기호를 나타내는 문자열의 길이 ≤ 20 (※기호에 매치하는 문자열의 길이가 아님에 주의)

출력

총수를 1,000,000,007로 나눈 나머지

예제3

예제 1
입력
```
1 0 1 0
3
dna: a b
a: [AT]
b: [GC]
```
예상 출력
```
1
```

예제 2

입력

1 1 1 2
1
k: [ATG] [ATG] [ATG] [C] [C]

예상 출력

예제 3

입력

3 1 1 1
3
inv: at b b b
at: [ATG] b
b: [C]

예상 출력