#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
static const LL MODVAL = 1000000007;
class DNADeletion {
public:
int differentProteins(vector <string> DNASequence, vector <string> codonTable)
{
string dna;
for(int i=0; i<DNASequence.size(); ++i) dna += DNASequence[i];
int N = dna.size();
vector<string> cL, cR;
for(int i=0; i<codonTable.size(); ++i) {
stringstream sin(codonTable[i]);
string s, t; sin>>s>>t;
cL.push_back(s);
cR.push_back(t);
}
int M = cL.size();
vector<LL> dp(N+1); dp[0] = 1;
for(int i=0; i<N; ++i)
{
// there's dp[i] ways to generate some aminoseq from dna[0...i]
vector<int> p(M);
set<string> done;
for(int j=i; j<dna.size(); ++j)
{
for(int k=0; k<M; ++k)
if( p[k]<3 && dna[j]==cL[k][p[k]] ) {
p[k]++;
if( p[k]==3 && !done.count(cR[k]) ) {
done.insert(cR[k]);
dp[j+1] = (dp[j+1] + dp[i]) % MODVAL;
}
}
}
}
LL n = (accumulate(dp.begin(), dp.end(), 0LL) - 1) % MODVAL;
return int(n);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const int &Expected, const int &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
string DNASequence_[] = {"ACTG"};
vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
string codonTable_[] = {"ACT gua", "ACG cys", "ATG leu", "CTG thr"};
vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
int RetVal = 4;
return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
int Test_(Case_<1>) {
string DNASequence_[] = {"AAACCC"};
vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
string codonTable_[] = {"AAA thr", "CCC cys"};
vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
int RetVal = 3;
return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
int Test_(Case_<2>) {
string DNASequence_[] = {"AAATCCC"};
vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
string codonTable_[] = {"AAA gua","TCC dop","AAT dop","CCC gua"};
vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
int RetVal = 5;
return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
int Test_(Case_<3>) {
string DNASequence_[] = {"ATGCGCATTAACCTCCTACCATGGAAGGGACGTAACCCGGCAATTTGATC",
"CTGATGACGGCATAAGCTACCCCTAGAGGTAAAAATGCATACTGCGTGCT",
"ATGCAG"};
vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
string codonTable_[] = {"AAC RpjZt","AAT ZeiC","GCA ChZwh","TCC RpjZt","GAA I",
"TAG ZeiC","CTG dVK","GAG ZeiC","GTG I","AAG q","ATT dVK",
"AGA cJEjM","GGG KONUd","GTC ZRV","GGC ZeiC","TTA KONUd",
"GAC q","CCA q","GCC ZRV","GCG RpjZt","CCT ZRV","ATG dVK",
"ATC ChZwh","CTC cJEjM","CCC q","ATA dWjz","TTG DkEG",
"CAG q","CAA ZRV","ACT dVK","TCG dVK","ACC I","CGC dVK"};
vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
int RetVal = 455985264;
return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
int Test_(Case_<4>) {
string DNASequence_[] = {"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"};
vector <string> DNASequence(DNASequence_, DNASequence_+sizeof(DNASequence_)/sizeof(*DNASequence_));
string codonTable_[] = {"AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys","AAA thr", "CCC cys", "CCC cys", "CCC cys", "CCC cys"};
vector <string> codonTable(codonTable_, codonTable_+sizeof(codonTable_)/sizeof(*codonTable_));
int RetVal = 3;
return verify_case(RetVal, DNADeletion().differentProteins(DNASequence, codonTable)); }
template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<> void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE