DNA

Time limit2sMemory limit512 MB

Summary

Given a context-free grammar over DNA letters and target counts of A, T, G, C, count the strings the grammar generates with exactly those letter counts, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

A gene is a string over A, T, G, C. Strangely, the genes in this world are known to follow a certain grammar.

The grammar is given in the following form.

nonterminal1: symbol1_1 symbol1_2 ... symbol1_n1
nonterminal2: symbol2_1 symbol2_2 ... symbol2_n2
...
nonterminalm: symbolm_1 symbolm_2 ... symbolm_nm

Each symbol is either a nonterminal or a terminal. A nonterminal is written as a lowercase string, and a terminal is written as some characters among A, T, G, C enclosed in "[" and "]".

An example of a grammar is the following.

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

The line "nonterminali: symboli_1 symboli_2 ... symboli_ni" is called the rule of nonterminal i, and there is exactly one rule for each nonterminal appearing in the grammar.

A string s "matches" nonterminal i when there exist substrings {sj} of s with s = s1 + s2 + ... + sni such that sj (1 ≤ j ≤ ni) matches symbol j in the rule.

A string s "matches" a terminal when the string consists of one character and that character is contained in the string representing the terminal.

A string follows the grammar when it matches nonterminal 1.

Rule i does not contain, among its symbols, a nonterminal j with j ≤ i.

You are given the grammar and four integers Na, Nt, Ng, Nc. Find the number of genes that follow the grammar and contain exactly Na occurrences of A, exactly Nt occurrences of T, exactly Ng occurrences of G, and exactly Nc occurrences of C, modulo 1,000,000,007.

Input

Na Nt Ng Nc
m
nonterminal1: symbol11 symbol12 ... symbol1n1
nonterminal2: symbol21 symbol22 ... symbol2n2
...
nonterminalm: symbolm1 symbolm2 ... symbolmnm

0 ≤ Na, Nt, Ng, Nc ≤ 50
1 ≤ m ≤ 50
1 ≤ ni ≤ 10
1 ≤ length of a string representing a symbol ≤ 20 (note that this is not the length of a string matching the symbol)

Output

The number of genes modulo 1,000,000,007

Examples3

Example 1
Input
```
1 0 1 0
3
dna: a b
a: [AT]
b: [GC]
```
Expected output
```
1
```

Example 2

Input

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

Expected output

Example 3

Input

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

Expected output