#include<iostream>#include<sstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>using namespace std;const double eps(1e-8);typedef long long lint;#define clr(x) memset( x , 0 , sizeof(x) )#define sz(v) ((int)(v).size())#define rep(i, n) for (int i = 0; i < (n); ++i)#define repf(i, a, b) for (int i = (a); i <= (b); ++i)#define repd(i, a, b) for (int i = (a); i >= (b); --i)#define clrs( x , y ) memset( x , y , sizeof(x) )const int maxn = 1000 + 10;int vs[maxn], vt[maxn], v[maxn];int n, m, len, S, tn;char word[maxn];vector<int> e[maxn], wo[maxn], g[maxn];void add(vector<int> *e, vector<int> *wo, int x, int y, int w) { e[x].push_back(y); wo[x].push_back(w);}void add2(int x, int y) { g[x].push_back(y);}void init() { scanf("%s", word); m = strlen(word); scanf("%d", &n); scanf("%d%d", &S, &tn); clr(vs); clr(vt); S--; vs[S] = 1; rep (i, tn) { int x; scanf("%d", &x); x--; vt[x] = 1; } rep (i, n) { e[i].clear(); g[i].clear(); wo[i].clear(); } rep (i, n) rep (j, m) { int x; scanf("%d", &x); x--; add(e, wo, i, x, j); } rep (i, n) rep (j, m) { int x; scanf("%d", &x); add2(i, x); } scanf("%d", &len);}int dfs(int x, int w) { if (v[x]) return -1; v[x] = 1; rep (i, sz(e[x])) { if (w == wo[x][i]) { int j = e[x][i]; if (g[x][i]){ int h = dfs(j, w); if (h == -1) return -1; e[x][i] = h; g[x][i] = 0; return h; } else if (!g[x][i]) { return j; } } } return -1;}void getG2() { rep (i, n) { rep (k, sz(e[i])) { if (g[i][k]) { memset(v, 0, sizeof(v)); dfs(i, wo[i][k]); } } } }void add(vector<int> &a, vector<int> b) { int an = sz(a), bn = sz(b); rep (i, min(an, bn)) { a[i] += b[i]; } repf (i, an, bn - 1) { a.push_back(b[i]); } rep (i, max(an, bn)) { if (a[i] >= 10) { if (i + 1 >= sz(a)) a.push_back(0); a[i + 1] += a[i] / 10; a[i] %= 10; } }}void myset(vector<int> &a, int w) { a.clear(); a.push_back(w);}void myput(vector<int> &a) { repd (i, sz(a) - 1, 0) { printf("%d", a[i]); } puts("");}vector<int> f[70][maxn];void gao(int l, int w) { if (sz(f[l][w]) != 0) return; if (l == 0) { if (vt[w] == 0) { myset(f[l][w], 0); } else { myset(f[l][w], 1); } return ; } myset(f[l][w], 0); rep (i, sz(e[w])) { int j = e[w][i]; if (g[w][i] == 0) { gao(l - 1, j); add(f[l][w], f[l - 1][j]); } }}void workDP() { repf (i, 0, len) repf (j, 0, n) f[i][j].clear(); gao(len, S); myput(f[len][S]);}int main(){ int T; scanf("%d", &T); rep(ca, T) { if (ca != 0) puts(""); init(); getG2(); workDP(); } return 0;}
