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

inputFormat

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)

outputFormat

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

样例

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

6