#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
template<typename T>
struct DP3
{
int N1, N2, N3;
vector<T> data;
DP3(){}
DP3(int N1, int N2, int N3, const T& t = T())
: N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
T& operator()(int i1, int i2, int i3)
{ return data[ ((i1*N2)+i2)*N3+i3 ]; }
void swap(DP3& rhs)
{ data.swap(rhs.data); }
};
class GameWithGraphAndTree { public:
vector<string> graph;
vector< vector<int> > children;
vector<int> subtree_size;
int calc(vector <string> graph_, vector <string> tree_)
{
int N = graph_.size();
graph = graph_;
children.resize(N);
subtree_size.resize(N);
computeChildren(-1, 0, tree_);
memo = DP3<LL>(N,N,1<<N,-1);
LL answer = 0;
for(int gv=0; gv<graph.size(); ++gv)
answer += vertical(0, gv, (1<<N)-1);
return int(answer % 1000000007);
}
void computeChildren(int tparent, int tv, const vector<string>& tree)
{
subtree_size[tv] = 1;
for(int tc=0; tc<tree.size(); ++tc)
if( tree[tv][tc] == 'Y' && tc!=tparent ) {
children[tv].push_back(tc);
computeChildren(tv, tc, tree);
subtree_size[tv] += subtree_size[tc];
}
}
LL vertical(int tv, int gv, int mask)
{
return horizontal(tv, gv, mask&~(1<<gv), 0);
}
DP3<LL> memo;
LL horizontal(int tv, int gv, int mask, int i)
{
if( i == children[tv].size() )
return 1;
int tu = children[tv][i];
if( memo(tv,gv,mask) >= 0 )
return memo(tv,gv,mask);
LL answer = 0;
for(int subset=mask; subset; subset=(subset-1)&mask)
if( __builtin_popcount(subset) == subtree_size[tu] )
for(int gu=0; (1<<gu)<=subset; ++gu)
if( graph[gv][gu]=='Y' && ((1<<gu)&subset) )
answer += vertical(tu, gu, subset) * horizontal(tv, gv, mask&~subset, i+1);
return memo(tv,gv,mask) = answer % 1000000007;
}
};
// 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> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, GameWithGraphAndTree().calc(graph, tree));}
int main(){
CASE(0)
string graph_[] = {"NYN",
"YNY",
"NYN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {"NYY",
"YNN",
"YNN"};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 2;
END
CASE(1)
string graph_[] = {"NYNNN",
"YNYYY",
"NYNYY",
"NYYNY",
"NYYYN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {"NYNNN",
"YNYNN",
"NYNYN",
"NNYNY",
"NNNYN"};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 12;
END
CASE(2)
string graph_[] = {"NYNNNY",
"YNYNNN",
"NYNYNN",
"NNYNYN",
"NNNYNY",
"YNNNYN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {"NYNNYN",
"YNNYNY",
"NNNNYN",
"NYNNNN",
"YNYNNN",
"NYNNNN"};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 0;
END
CASE(3)
string graph_[] = {"NYNNYN",
"YNNYNY",
"NNNNYN",
"NYNNNN",
"YNYNNN",
"NYNNNN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {"NNNYYN",
"NNYNNN",
"NYNNYY",
"YNNNNN",
"YNYNNN",
"NNYNNN"};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 2;
END
CASE(4)
string graph_[] = {"NYNNNYNNY",
"YNNNNNNYN",
"NNNNYYNYY",
"NNNNNYNNY",
"NNYNNNYNY",
"YNYYNNNYN",
"NNNNYNNYN",
"NYYNNYYNN",
"YNYYYNNNN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {"NNYNNNYYN",
"NNNNYNNNN",
"YNNNNNNNN",
"NNNNNNYNN",
"NYNNNNNYY",
"NNNNNNNNY",
"YNNYNNNNN",
"YNNNYNNNN",
"NNNNYYNNN"};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 90;
END
CASE(5)
string graph_[] = {"N"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {"N"};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 1;
END
CASE(6)
string graph_[] = {
"NYYYYYYYYYYYYY",
"YNYYYYYYYYYYYY",
"YYNYYYYYYYYYYY",
"YYYNYYYYYYYYYY",
"YYYYNYYYYYYYYY",
"YYYYYNYYYYYYYY",
"YYYYYYNYYYYYYY",
"YYYYYYYNYYYYYY",
"YYYYYYYYNYYYYY",
"YYYYYYYYYNYYYY",
"YYYYYYYYYYNYYY",
"YYYYYYYYYYYNYY",
"YYYYYYYYYYYYNY",
"YYYYYYYYYYYYYN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {
"NYNNNNNNNNNNNN",
"YNYNNNNNNNNNNN",
"NYNYNNNNNNNNNN",
"NNYNYNNNNNNNNN",
"NNNYNYNNNNNNNN",
"NNNNYNYNNNNNNN",
"NNNNNYNYNNNNNN",
"NNNNNNYNYNNNNN",
"NNNNNNNYNYNNNN",
"NNNNNNNNYNYNNN",
"NNNNNNNNNYNYNN",
"NNNNNNNNNNYNYN",
"NNNNNNNNNNNYNY",
"NNNNNNNNNNNNYN",
};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 178290591;
END
CASE(7)
string graph_[] = {
"NYYYYYYYYYYYYY",
"YNYYYYYYYYYYYY",
"YYNYYYYYYYYYYY",
"YYYNYYYYYYYYYY",
"YYYYNYYYYYYYYY",
"YYYYYNYYYYYYYY",
"YYYYYYNYYYYYYY",
"YYYYYYYNYYYYYY",
"YYYYYYYYNYYYYY",
"YYYYYYYYYNYYYY",
"YYYYYYYYYYNYYY",
"YYYYYYYYYYYNYY",
"YYYYYYYYYYYYNY",
"YYYYYYYYYYYYYN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {
"NYYYNNNNNNNNNN",
"YNNNYYYNNNNNNN",
"YNNNNNNYYYNNNN",
"YNNNNNNNNNYYYY",
"NYNNNNNNNNNNNN",
"NYNNNNNNNNNNNN",
"NYNNNNNNNNNNNN",
"NNYNNNNNNNNNNN",
"NNYNNNNNNNNNNN",
"NNYNNNNNNNNNNN",
"NNNYNNNNNNNNNN",
"NNNYNNNNNNNNNN",
"NNNYNNNNNNNNNN",
"NNNYNNNNNNNNNN",
};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 178290591;
END
CASE(8)
string graph_[] = {"NYYYYYYYYYYYYY", "YNYYYYYYYYYYYY", "YYNYYYYYYYYYYY", "YYYNYYYYYYYYYY", "YYYYNYYYYYYYYY", "YYYYYNYYYYYYYY", "YYYYYYNYYYYYYY", "YYYYYYYNYYYYYY", "YYYYYYYYNYYYYY", "YYYYYYYYYNYYYY", "YYYYYYYYYYNYYY", "YYYYYYYYYYYNYY", "YYYYYYYYYYYYNY", "YYYYYYYYYYYYYN"};
vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
string tree_[] = {"NYYYYYYYYYYYYY", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN", "YNNNNNNNNNNNNN"};
vector <string> tree(tree_, tree_+sizeof(tree_)/sizeof(*tree_));
int _ = 178290591;
END
}
// END CUT HERE