#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define pb push_back
#define ALL(x) x.begin(),x.end()

using namespace std;

typedef long long ll;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

#define A_ 0
#define T_ 1
#define G_ 2
#define C_ 3
#define NONTERMINAL 0
#define TERMINAL 1

struct Data {
  int type; // NONTERMINAL or TERMINAL
  int dst; // for NONTERMINAL
  int bit; // for TERMINAL
};

#define MAX 60
vector<int> N;
int m;
vector<Data> G[MAX];

const ll mod = 1000000007LL;

bool debug = 0;

inline int toIDX(char c) { if( c == 'A' ) return A_; if( c == 'T' ) return T_; if( c == 'G' ) return G_; if( c == 'C' ) return C_; assert(false); }
inline char toCHR(int  i) { if( i == A_ ) return 'A'; if( i == T_ ) return 'T'; if( i == G_ ) return 'G'; if( i == C_ ) return 'C'; assert(false); }


bool fail;
vector<int> chars;
int enum_char_dfs(int cur) {
  if( fail ) return -1;
  int ret = 0;
  rep(i,(int)G[cur].size()) {
    Data &d = G[cur][i];
    if( d.type == NONTERMINAL ) {
      ret += enum_char_dfs(d.dst);
      if( ret >= N[0] + N[1] + N[2] + N[3] + 1 ) { fail = true; return -1; }
    } else {
      chars.pb(d.bit);
      //++len;
      ++ret;
    }
  }
  return ret;
}

int dp[2][52][52][52][52];
int solve_DP(int L,int R) { //[L,R)
  memset(dp,0,sizeof dp);
  dp[0][0][0][0][0] = 1;
  int idx = 0;
  REP(i,L,R) {
    rep(w,N[0]+1) rep(x,N[1]+1) rep(y,N[2]+1) rep(z,N[3]+1) dp[(idx+1)&1][w][x][y][z] = 0;
    rep(a,N[0]+1) {
      rep(t,N[1]+1) {
	rep(g,N[2]+1) {
	  rep(c,N[3]+1) {
	    int &score = dp[idx&1][a][t][g][c];
	    if( score == 0 ) continue;
	    if( (chars[i]>>A_) & 1 ) ( dp[(idx+1)&1][a+1][t][g][c] += score ) %= mod;
	    if( (chars[i]>>T_) & 1 ) ( dp[(idx+1)&1][a][t+1][g][c] += score ) %= mod;
	    if( (chars[i]>>G_) & 1 ) ( dp[(idx+1)&1][a][t][g+1][c] += score ) %= mod;
	    if( (chars[i]>>C_) & 1 ) ( dp[(idx+1)&1][a][t][g][c+1] += score ) %= mod;
	  }
	}
      }
    }
    ++idx;
  }
  return idx;
}

const ll ccoef = 1000000;
const ll gcoef = 10000;
const ll tcoef = 100;
inline ll toHash(int a,int t,int g,int c) { return a + t * tcoef + g * gcoef + c * ccoef; }

void toMap(int idx, map<ll,ll> &mp) {
  rep(a,N[0]+1) {
    rep(t,N[1]+1) {
      rep(g,N[2]+1) {
	rep(c,N[3]+1) {
	  ll hs = toHash(a,t,g,c);
	  ll score = dp[idx][a][t][g][c];
	  if( score == 0 ) continue;
	  mp[hs] = score;
	}
      }
    }
  }
}

void solve() {
  if( debug ) {
    cout << "* Graph ---" << endl;
    rep(i,m) {
      cout << "  - i = " << i << "-th:" << endl;
      rep(j,(int)G[i].size()) {
	Data &d = G[i][j];
	if( d.type == NONTERMINAL ) {
	  cout << "  [NONTERMINAL] : to " << d.dst << endl;
	} else {
	  assert( d.bit != -1 );
	  bitset<4> BIT(d.bit);
	  cout << "  [   TERMINAL] : bit = " << BIT << endl;
	}
      }
      puts("");
    }
  }
  
  // enumerate chars
  chars.clear();
  fail = false;
  int len = enum_char_dfs(0);
  if( fail ) { puts("0"); return ; }
  if( debug ) {
    assert( len == (int)chars.size() );
    cout << "* enumerate chars ---" << endl;
    cout << "  - len = " << len << endl;
    cout << "    ";
    rep(i,len) {
      cout << "[";
      rep(j,4) {
	if( (chars[i]>>j) & 1 ) {
	  cout << toCHR(j);
	}
      }
      cout << "] ";
    }
    puts("");
  }

  // Dynamic Programming!!
  if( len > N[0] + N[1] + N[2] + N[3] ) { puts("0"); return ; }
  int sz = len / 2;
  if( debug ) {
    cout << "[SPLIT] -- [" << 0 << "," << sz << ") and [" << sz << "," << len << ")" << endl;
  }
  map<ll,ll> mp[2];
  int lst;
  lst = solve_DP(0,sz);
  toMap(lst&1,mp[0]);



  if( debug ) {
    cout << "* mp[0] Info ---" << endl;
    for(auto v : mp[0]) {
      ll hs = v.first;
      int c = hs / ccoef;
      hs -= ( c * ccoef );
      int g = hs / gcoef;
      hs -= ( g * gcoef );
      int t = hs / tcoef;
      hs -= ( t * tcoef );
      int a = hs;
      ll score = v.second;
      cout << "  (A,T,G,C) = (" << a << "," << t << "," << g << "," << c << ")" << endl;
      cout << "      score = " << score << endl;
    }
  }

  lst = solve_DP(sz,len);
  toMap(lst&1,mp[1]);
  if( debug ) {
    cout << "* mp[1] Info ---" << endl;
    for(auto v : mp[1]) {
      ll hs = v.first;
      int c = hs / ccoef;
      hs -= ( c * ccoef );
      int g = hs / gcoef;
      hs -= ( g * gcoef );
      int t = hs / tcoef;
      hs -= ( t * tcoef );
      int a = hs;
      ll score = v.second;
      cout << "  (A,T,G,C) = (" << a << "," << t << "," << g << "," << c << ")" << endl;
      cout << "      score = " << score << endl;
    }
  }

  // hanbun-zennrekkyo
  ll answer = 0;
  for(auto v : mp[0]) {
    ll hs = v.first;
    int c = hs / ccoef;
    hs -= ( c * ccoef );
    int g = hs / gcoef;
    hs -= ( g * gcoef );
    int t = hs / tcoef;
    hs -= ( t * tcoef );
    int a = hs;
    ll score = v.second;
    if( a > N[0] || t > N[1] || g > N[2] || c > N[3] ) continue;
    int rem_a = N[0] - a;
    int rem_t = N[1] - t;
    int rem_g = N[2] - g;
    int rem_c = N[3] - c;
    ll next_hs = toHash(rem_a,rem_t,rem_g,rem_c);
    if( mp[1].count(next_hs) ) {
      ( answer += ( ( score * mp[1][next_hs] ) % mod ) ) %= mod;
    }
  }
  cout << answer << endl;
}

void parse(string s, map<string,int> &mp, int &id) {
  rep(i,(int)s.size()) if( s[i] == ':' ) { s[i] = ' '; break; }
  stringstream ss;
  ss << s;
  vector<string> vec;
  while( ss >> s ) vec.pb(s);
  if( !mp.count(vec[0]) ) { mp[vec[0]] = id++; }
  int cur = mp[vec[0]];
  REP(i,1,(int)vec.size()) {
    string &t = vec[i];
    if( t[0] == '[' ) {
      int ptr = 1, bit = 0;
      while( ptr < (int)t.size() && t[ptr] != ']' ) bit = bit | (1<<toIDX(t[ptr++]));
      G[cur].pb((Data){TERMINAL,-1,bit});
    } else {
      if( !mp.count(vec[i]) ) { mp[vec[i]] = id++; }
      int nex = mp[vec[i]];
      G[cur].pb((Data){NONTERMINAL,nex,-1});
    }
  }
}

int main() {
  N.resize(4);
  rep(i,4) cin >> N[i];
  cin >> m;
  cin.ignore();
  string line;
  map<string,int> mp;
  int id=0;
  rep(i,m) {
    getline(cin,line);
    parse(line,mp,id);
  }
  solve();
  return 0;
}


### Prompt

Construct a cpp code solution to the problem outlined:

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<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define pb push_back
#define ALL(x) x.begin(),x.end()

using namespace std;

typedef long long ll;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

#define A_ 0
#define T_ 1
#define G_ 2
#define C_ 3
#define NONTERMINAL 0
#define TERMINAL 1

struct Data {
  int type; // NONTERMINAL or TERMINAL
  int dst; // for NONTERMINAL
  int bit; // for TERMINAL
};

#define MAX 60
vector<int> N;
int m;
vector<Data> G[MAX];

const ll mod = 1000000007LL;

bool debug = 0;

inline int toIDX(char c) { if( c == 'A' ) return A_; if( c == 'T' ) return T_; if( c == 'G' ) return G_; if( c == 'C' ) return C_; assert(false); }
inline char toCHR(int  i) { if( i == A_ ) return 'A'; if( i == T_ ) return 'T'; if( i == G_ ) return 'G'; if( i == C_ ) return 'C'; assert(false); }


bool fail;
vector<int> chars;
int enum_char_dfs(int cur) {
  if( fail ) return -1;
  int ret = 0;
  rep(i,(int)G[cur].size()) {
    Data &d = G[cur][i];
    if( d.type == NONTERMINAL ) {
      ret += enum_char_dfs(d.dst);
      if( ret >= N[0] + N[1] + N[2] + N[3] + 1 ) { fail = true; return -1; }
    } else {
      chars.pb(d.bit);
      //++len;
      ++ret;
    }
  }
  return ret;
}

int dp[2][52][52][52][52];
int solve_DP(int L,int R) { //[L,R)
  memset(dp,0,sizeof dp);
  dp[0][0][0][0][0] = 1;
  int idx = 0;
  REP(i,L,R) {
    rep(w,N[0]+1) rep(x,N[1]+1) rep(y,N[2]+1) rep(z,N[3]+1) dp[(idx+1)&1][w][x][y][z] = 0;
    rep(a,N[0]+1) {
      rep(t,N[1]+1) {
	rep(g,N[2]+1) {
	  rep(c,N[3]+1) {
	    int &score = dp[idx&1][a][t][g][c];
	    if( score == 0 ) continue;
	    if( (chars[i]>>A_) & 1 ) ( dp[(idx+1)&1][a+1][t][g][c] += score ) %= mod;
	    if( (chars[i]>>T_) & 1 ) ( dp[(idx+1)&1][a][t+1][g][c] += score ) %= mod;
	    if( (chars[i]>>G_) & 1 ) ( dp[(idx+1)&1][a][t][g+1][c] += score ) %= mod;
	    if( (chars[i]>>C_) & 1 ) ( dp[(idx+1)&1][a][t][g][c+1] += score ) %= mod;
	  }
	}
      }
    }
    ++idx;
  }
  return idx;
}

const ll ccoef = 1000000;
const ll gcoef = 10000;
const ll tcoef = 100;
inline ll toHash(int a,int t,int g,int c) { return a + t * tcoef + g * gcoef + c * ccoef; }

void toMap(int idx, map<ll,ll> &mp) {
  rep(a,N[0]+1) {
    rep(t,N[1]+1) {
      rep(g,N[2]+1) {
	rep(c,N[3]+1) {
	  ll hs = toHash(a,t,g,c);
	  ll score = dp[idx][a][t][g][c];
	  if( score == 0 ) continue;
	  mp[hs] = score;
	}
      }
    }
  }
}

void solve() {
  if( debug ) {
    cout << "* Graph ---" << endl;
    rep(i,m) {
      cout << "  - i = " << i << "-th:" << endl;
      rep(j,(int)G[i].size()) {
	Data &d = G[i][j];
	if( d.type == NONTERMINAL ) {
	  cout << "  [NONTERMINAL] : to " << d.dst << endl;
	} else {
	  assert( d.bit != -1 );
	  bitset<4> BIT(d.bit);
	  cout << "  [   TERMINAL] : bit = " << BIT << endl;
	}
      }
      puts("");
    }
  }
  
  // enumerate chars
  chars.clear();
  fail = false;
  int len = enum_char_dfs(0);
  if( fail ) { puts("0"); return ; }
  if( debug ) {
    assert( len == (int)chars.size() );
    cout << "* enumerate chars ---" << endl;
    cout << "  - len = " << len << endl;
    cout << "    ";
    rep(i,len) {
      cout << "[";
      rep(j,4) {
	if( (chars[i]>>j) & 1 ) {
	  cout << toCHR(j);
	}
      }
      cout << "] ";
    }
    puts("");
  }

  // Dynamic Programming!!
  if( len > N[0] + N[1] + N[2] + N[3] ) { puts("0"); return ; }
  int sz = len / 2;
  if( debug ) {
    cout << "[SPLIT] -- [" << 0 << "," << sz << ") and [" << sz << "," << len << ")" << endl;
  }
  map<ll,ll> mp[2];
  int lst;
  lst = solve_DP(0,sz);
  toMap(lst&1,mp[0]);



  if( debug ) {
    cout << "* mp[0] Info ---" << endl;
    for(auto v : mp[0]) {
      ll hs = v.first;
      int c = hs / ccoef;
      hs -= ( c * ccoef );
      int g = hs / gcoef;
      hs -= ( g * gcoef );
      int t = hs / tcoef;
      hs -= ( t * tcoef );
      int a = hs;
      ll score = v.second;
      cout << "  (A,T,G,C) = (" << a << "," << t << "," << g << "," << c << ")" << endl;
      cout << "      score = " << score << endl;
    }
  }

  lst = solve_DP(sz,len);
  toMap(lst&1,mp[1]);
  if( debug ) {
    cout << "* mp[1] Info ---" << endl;
    for(auto v : mp[1]) {
      ll hs = v.first;
      int c = hs / ccoef;
      hs -= ( c * ccoef );
      int g = hs / gcoef;
      hs -= ( g * gcoef );
      int t = hs / tcoef;
      hs -= ( t * tcoef );
      int a = hs;
      ll score = v.second;
      cout << "  (A,T,G,C) = (" << a << "," << t << "," << g << "," << c << ")" << endl;
      cout << "      score = " << score << endl;
    }
  }

  // hanbun-zennrekkyo
  ll answer = 0;
  for(auto v : mp[0]) {
    ll hs = v.first;
    int c = hs / ccoef;
    hs -= ( c * ccoef );
    int g = hs / gcoef;
    hs -= ( g * gcoef );
    int t = hs / tcoef;
    hs -= ( t * tcoef );
    int a = hs;
    ll score = v.second;
    if( a > N[0] || t > N[1] || g > N[2] || c > N[3] ) continue;
    int rem_a = N[0] - a;
    int rem_t = N[1] - t;
    int rem_g = N[2] - g;
    int rem_c = N[3] - c;
    ll next_hs = toHash(rem_a,rem_t,rem_g,rem_c);
    if( mp[1].count(next_hs) ) {
      ( answer += ( ( score * mp[1][next_hs] ) % mod ) ) %= mod;
    }
  }
  cout << answer << endl;
}

void parse(string s, map<string,int> &mp, int &id) {
  rep(i,(int)s.size()) if( s[i] == ':' ) { s[i] = ' '; break; }
  stringstream ss;
  ss << s;
  vector<string> vec;
  while( ss >> s ) vec.pb(s);
  if( !mp.count(vec[0]) ) { mp[vec[0]] = id++; }
  int cur = mp[vec[0]];
  REP(i,1,(int)vec.size()) {
    string &t = vec[i];
    if( t[0] == '[' ) {
      int ptr = 1, bit = 0;
      while( ptr < (int)t.size() && t[ptr] != ']' ) bit = bit | (1<<toIDX(t[ptr++]));
      G[cur].pb((Data){TERMINAL,-1,bit});
    } else {
      if( !mp.count(vec[i]) ) { mp[vec[i]] = id++; }
      int nex = mp[vec[i]];
      G[cur].pb((Data){NONTERMINAL,nex,-1});
    }
  }
}

int main() {
  N.resize(4);
  rep(i,4) cin >> N[i];
  cin >> m;
  cin.ignore();
  string line;
  map<string,int> mp;
  int id=0;
  rep(i,m) {
    getline(cin,line);
    parse(line,mp,id);
  }
  solve();
  return 0;
}


```