p01551 DNA
A gene is a string consisting of `A`,` T`, `G`,` C`. The genes in this world are strangely known to obey certain syntactic rules.

Syntax rules are given in the following form:


Non-terminal symbol 1: Symbol 1_1 Symbol 1_2 ... Symbol 1_n1
Non-terminal symbol 2: Symbol 2_1 Symbol 2_2 ... Symbol 2_n2
...
Non-terminal symbol m: symbol m_1 symbol m_2 ... symbol m_nm


The symbol is either a nonterminal symbol or a terminal symbol. Non-terminal symbols are represented by lowercase strings, and terminal symbols are some of the characters `A`,` T`, `G`,` C` surrounded by "` [` "and" `]` ". It is represented by a character string.

An example syntax rule looks like this:


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


"` Nonterminal symbol i: Symbol i_1 Symbol i_2 ... Symbol i_ni` "is called a rule for nonterminal symbol i, and there is exactly one rule for each nonterminal symbol that appears in the syntax rule.

A string s "` matches `" with the nonterminal i means that there is a substring {sj} of s such that s = s1 + s2 + ... + sni, and sj (1 ≤ j ≤ It means that ni) matches the symbol j in the rule.

When the string s "` matches `" with a terminal symbol, it means that the string consists of one character and that character is included in the string representing the terminal symbol.

A string that follows syntax rules means that it matches nonterminal symbol 1.

Rule i does not include the nonterminal symbol j (j ≤ i) in the symbol.

Given the syntax rules and the four integers Na, Nt, Ng, Nc. According to the syntax rules, find the remainder of the total number of genes that contain exactly Na for A, just Nt for T, just Ng for G, and just Nc for C, divided by 1,000,000,007.



Input

> Na Nt Ng Nc
> m
> Nonterminal 1: Symbol 11 Symbol 12 ... Symbol 1n1
> Non-terminal symbol 2: Symbol 21 Symbol 22 ... Symbol 2n2
> ...
> Non-terminal symbol m: symbol m1 symbol m2 ... symbol mnm
>

0 ≤ Na, Nt, Ng, Nc ≤ 50

1 ≤ m ≤ 50

1 ≤ ni ≤ 10

1 ≤ Length of the character string representing the symbol ≤ 20 (* Note that it is not the length of the character string that matches the symbol)

Output

The remainder of the total number divided by 1,000,000,007

Examples

Input

1 0 1 0
3
dna: a b
a: [AT]
b: [GC]


Output

1


Input

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


Output

6


Input

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


Output

0
```python
from collections import defaultdict
import sys
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    MOD = 10**9 + 7
    Na, Nt, Ng, Nc = map(int, readline().split())
    L = Na + Nt + Ng + Nc
    M = int(readline())
    MP = {}
    S = []
    for i in range(M):
        s = readline().strip()
        s1, s2 = s.split(": ")
        MP[s1] = s2.split(" ")
        S.append(s1)
    R = []
    memo = {}
    def dfs(s):
        if s in memo:
            return memo[s]
        r = []
        for e in MP[s]:
            if e[0] == "[":
                w = 0
                for v in map("ATGC".index, e[1:-1]):
                    w |= 1 << v
                r.append(w)
            else:
                r0 = dfs(e)
                if r0 is None:
                    return None
                r.extend(r0)
        if len(r) > L:
            return None
        memo[s] = r
        return r
    res = dfs(S[0])
    if res is None or len(res) < L:
        write("0\n")
        return
    L = len(res)

    T = [defaultdict(int) for i in range(L+1)]
    T[0][Na, Nt, Ng, Nc] = 1
    for k in range(L):
        s = res[k]
        p0 = s & 1; p1 = s & 2; p2 = s & 4; p3 = s & 8
        T1 = T[k+1]
        for (a, b, c, d), v in T[k].items():
            v %= MOD
            if p0 and a:
                T1[a-1, b, c, d] += v
            if p1 and b:
                T1[a, b-1, c, d] += v
            if p2 and c:
                T1[a, b, c-1, d] += v
            if p3 and d:
                T1[a, b, c, d-1] += v
    write("%d\n" % (T[L][0, 0, 0, 0] % MOD))
solve()

```