#include <bits/stdc++.h>
#define fir first
#define sec second

const int mod = 10000;
const int maxn = 55;
int n,m,a,b,k;

struct matrix {
	int g[maxn][maxn];
	matrix() {
		memset(g , 0 , sizeof(g));
	}
	void clear() {
		memset(g , 0 , sizeof(g));
	}
	void init() {
		for(int i = 0;i < n;++ i)
			g[i][i] = 1;
		return ;
	}
	matrix operator * (const matrix& p)const {
		matrix c;
		for(int k = 0;k < n;++ k)
			for(int i = 0;i < n;++ i)
				for(int j = 0;j < n;++ j)
					(c.g[i][j] += g[i][k] * p.g[k][j]) %= mod;
		return c;
	}
}f,g[15],G;

int cnt;
bool ins[15][maxn];
std::pair<int,int> E[50005];

matrix power(matrix x,int y) {
	matrix ans;
	ans.init();
	for(;y;y >>= 1) {
		if(y & 1)ans = ans * x;
		x = x * x;
	}
	return ans;
}

int main() {
	freopen("swamp.in","r",stdin);
	freopen("swamp.out","w",stdout);
	scanf("%d %d %d %d %d",&n,&m,&a,&b,&k);
	for(int i = 1;i <= m;++ i) {
		int u,v;
		scanf("%d %d",&u,&v);
		E[++ cnt] = {u , v};
		E[++ cnt] = {v , u};
	}
	int Q;
	scanf("%d",&Q);
	while(Q --) {
		int x,p[4] = {0};
		scanf("%d",&x);
		for(int i = 0;i < x;++ i)
			scanf("%d",&p[i]);
		for(int t = 1;t <= 12;++ t)
			ins[t][p[t % x]] = true;
	}
	for(int t = 1;t <= 12;++ t) {
		for(int i = 1;i <= cnt;++ i) {
			if(ins[t][E[i].sec])continue ;
			++ g[t].g[E[i].fir][E[i].sec];
		}
	}
	f.g[0][a] = 1;
	G.init();
	for(int t = 1;t <= 12;++ t)
		G = G * g[t];
	G = power(G , k / 12);
	k %= 12;
	for(int t = 1;t <= k;++ t)
		G = G * g[t];
	f = f * G;
	printf("%d\n",f.g[0][b]);
	return 0;
}