#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <cstring>
using namespace std;

vector<string> split(string s,const string &t) {
  vector<string> v;
  for (int p = 0; (p = s.find(t)) != s.npos; ) {
    v.push_back(s.substr(0,p));
    s = s.substr(p+t.size());
  }
  v.push_back(s);
  return v;
}

typedef long long ll;
const int MAX_LEN = 201;
const ll mod = 1000000007ll;
ll dp[52][52][52][52];
int Na,Nt,Ng,Nc;
int m;

map<string, vector<string> > rules;

void update(const char symbol,const int sum) {
  for (int a = 0; a <= sum && a <= Na; ++a) {
    for (int t = 0; a+t <= sum && t <= Nt; ++t) {
      for (int g = 0; a+t+g <= sum && g <= Ng; ++g) {
        int c = sum-a-t-g;
        if (c > Nc) continue;
        switch(symbol) {
        case 'A':
          dp[a+1][t][g][c] += dp[a][t][g][c];
          dp[a+1][t][g][c] %= mod;
          break;
        case 'T':
          dp[a][t+1][g][c] += dp[a][t][g][c];
          dp[a][t+1][g][c] %= mod;
          break;
        case 'G':
          dp[a][t][g+1][c] += dp[a][t][g][c];
          dp[a][t][g+1][c] %= mod;
          break;
        case 'C':
          dp[a][t][g][c+1] += dp[a][t][g][c];
          dp[a][t][g][c+1] %= mod;
          break;
        }
      }
    }
  }
}

vector<string> terminals;

void dfs(const string &rule) {
  const vector<string> &children = rules[rule];
  for(vector<string>::const_iterator it = children.begin();
      it != children.end(); ++it) {
    const string &term = *it;
    if(terminals.size() > Na+Nt+Nc+Ng) break;
    if(term[0] == '[') {
      // terminal
      terminals.push_back(term);
      if(terminals.size() > Na+Nt+Nc+Ng) break;
    } else {
      dfs(term);
    }
  }
}

int main() {
  cin>>Na>>Nt>>Ng>>Nc;
  cin>>m; cin.ignore();
  terminals.clear();

  string firstRule = "";
  string line;
  for (int i=0; i<m; ++i) {
    getline(cin, line);
    vector<string> vs = split(line, " ");
    vector<string> children;
    for (int j=1; j<vs.size(); ++j) children.push_back(vs[j]);
    rules[vs[0].substr(0,vs[0].length()-1)] = children;
    if (firstRule == "") firstRule = vs[0].substr(0,vs[0].length()-1);
  }

  memset(dp, 0, sizeof(dp));
  dp[0][0][0][0] = 1;
  dfs(firstRule);
  if (terminals.size() != Na+Nt+Nc+Ng) {
    cout<<0<<endl;
    return 0;
  }

  for (int i=0; i<terminals.size(); ++i) {
    const string &term = terminals[i];
    for (int j=1; j<term.length()-1; ++j)
      update(term[j], i);
  }
  cout<<dp[Na][Nt][Ng][Nc]<<endl;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

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

### Response

```cpp
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <cstring>
using namespace std;

vector<string> split(string s,const string &t) {
  vector<string> v;
  for (int p = 0; (p = s.find(t)) != s.npos; ) {
    v.push_back(s.substr(0,p));
    s = s.substr(p+t.size());
  }
  v.push_back(s);
  return v;
}

typedef long long ll;
const int MAX_LEN = 201;
const ll mod = 1000000007ll;
ll dp[52][52][52][52];
int Na,Nt,Ng,Nc;
int m;

map<string, vector<string> > rules;

void update(const char symbol,const int sum) {
  for (int a = 0; a <= sum && a <= Na; ++a) {
    for (int t = 0; a+t <= sum && t <= Nt; ++t) {
      for (int g = 0; a+t+g <= sum && g <= Ng; ++g) {
        int c = sum-a-t-g;
        if (c > Nc) continue;
        switch(symbol) {
        case 'A':
          dp[a+1][t][g][c] += dp[a][t][g][c];
          dp[a+1][t][g][c] %= mod;
          break;
        case 'T':
          dp[a][t+1][g][c] += dp[a][t][g][c];
          dp[a][t+1][g][c] %= mod;
          break;
        case 'G':
          dp[a][t][g+1][c] += dp[a][t][g][c];
          dp[a][t][g+1][c] %= mod;
          break;
        case 'C':
          dp[a][t][g][c+1] += dp[a][t][g][c];
          dp[a][t][g][c+1] %= mod;
          break;
        }
      }
    }
  }
}

vector<string> terminals;

void dfs(const string &rule) {
  const vector<string> &children = rules[rule];
  for(vector<string>::const_iterator it = children.begin();
      it != children.end(); ++it) {
    const string &term = *it;
    if(terminals.size() > Na+Nt+Nc+Ng) break;
    if(term[0] == '[') {
      // terminal
      terminals.push_back(term);
      if(terminals.size() > Na+Nt+Nc+Ng) break;
    } else {
      dfs(term);
    }
  }
}

int main() {
  cin>>Na>>Nt>>Ng>>Nc;
  cin>>m; cin.ignore();
  terminals.clear();

  string firstRule = "";
  string line;
  for (int i=0; i<m; ++i) {
    getline(cin, line);
    vector<string> vs = split(line, " ");
    vector<string> children;
    for (int j=1; j<vs.size(); ++j) children.push_back(vs[j]);
    rules[vs[0].substr(0,vs[0].length()-1)] = children;
    if (firstRule == "") firstRule = vs[0].substr(0,vs[0].length()-1);
  }

  memset(dp, 0, sizeof(dp));
  dp[0][0][0][0] = 1;
  dfs(firstRule);
  if (terminals.size() != Na+Nt+Nc+Ng) {
    cout<<0<<endl;
    return 0;
  }

  for (int i=0; i<terminals.size(); ++i) {
    const string &term = terminals[i];
    for (int j=1; j<term.length()-1; ++j)
      update(term[j], i);
  }
  cout<<dp[Na][Nt][Ng][Nc]<<endl;
}
```