#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>
using namespace std;
typedef long long LL;
static const int MODNUM = 1000000007;
// make [i,j) by k[z..$]
LL dp[31][31][51][51];
class ReverseResources
{
public:
int findDecompositions(string str, vector <string> resources)
{
memset(dp, 0xff, sizeof(dp));
LL sum = 0;
for(int k=0; k<resources.size(); ++k)
sum = (sum + rec(0, str.size(), k, 0, str, resources, dp)) % MODNUM;
return sum;
}
LL rec(int i, int j, int k, int z, string& s, vector<string>& rs, LL dp[31][31][51][51] )
{
if( dp[i][j][k][z] >= 0 )
return dp[i][j][k][z];
string& r = rs[k];
if( z==r.size() )
return dp[i][j][k][z] = (i==j ? 1 : 0);
if( r[z] == '%' )
{
LL sum = 0;
if( z+2 == r.size() )
{
for(int kk=0; kk<rs.size(); ++kk)
sum = (sum + rec(i, j, kk, 0, s, rs, dp)) % MODNUM;
}
else
{
for(int jj=i+1; jj<j; ++jj)
{
LL right = rec(jj, j, k, z+2, s, rs, dp);
if( right ) {
LL left = 0;
for(int kk=0; kk<rs.size(); ++kk)
left = (left + rec(i, jj, kk, 0, s, rs, dp)) % MODNUM;
sum = (sum + left*right) % MODNUM;
}
}
}
return dp[i][j][k][z] = sum;
}
else
{
if( r[z]==s[i] && i+1<=j )
return dp[i][j][k][z] = rec(i+1,j,k,z+1,s,rs,dp);
else
return dp[i][j][k][z] = 0;
}
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); }
private:
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(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arg0 = "Error in module foo, code 123."; string Arr1[] = {"foo", "123", "Error in module %s.", "%s, code %s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 1; verify_case(0, Arg2, findDecompositions(Arg0, Arg1)); }
void test_case_1() { string Arg0 = "The fox jumped over the dog."; string Arr1[] = {"The fox %s over the dog.",
"lazy",
"brown",
"jump%s",
"s",
"ed",
"The %s",
"fox %s",
"%s over %s",
"the dog."}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 5; verify_case(1, Arg2, findDecompositions(Arg0, Arg1)); }
void test_case_2() { string Arg0 = "abcde"; string Arr1[] = {"%sc%s", "b", "de", "a%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(2, Arg2, findDecompositions(Arg0, Arg1)); }
void test_case_3() { string Arg0 = "abcde"; string Arr1[] = {"%se", "a%s", "%sb%s", "%sc%s", "%sd%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; verify_case(3, Arg2, findDecompositions(Arg0, Arg1)); }
void test_case_4() { string Arg0 = "aaaaa"; string Arr1[] = {"a","%s%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 14; verify_case(4, Arg2, findDecompositions(Arg0, Arg1)); }
void test_case_5() { string Arg0 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"; string Arr1[] = {"a","aa","%s%s","%sa","a%s","aaa","aa%s","a%sa",
"a%s%s","%saa","%sa%s","%s%sa","%s%s%s","aaaa",
"aaa%s","aa%sa","aa%s%s","a%saa","a%sa%s","a%s%sa",
"a%s%s%s","%saaa","%saa%s","%sa%sa","%sa%s%s",
"%s%saa","%s%sa%s","%s%s%sa","%s%s%s%s","aaaaa",
"aaaa%s","aaa%sa","aaa%s%s","aa%saa","aa%sa%s",
"aa%s%sa","aa%s%s%s","a%saaa","a%saa%s","a%sa%sa",
"a%sa%s%s","a%s%saa","a%s%sa%s","a%s%s%sa",
"a%s%s%s%s","%saaaa","%saaa%s","%saa%sa","%saa%s%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 879704799; verify_case(5, Arg2, findDecompositions(Arg0, Arg1)); }
void test_case_6() { string Arg0 = "aa"; string Arr1[] = {"a", "a", "%s%s", "%s%s"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 8; verify_case(6, Arg2, findDecompositions(Arg0, Arg1)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main() { ReverseResources().run_test(-1); }
// END CUT HERE