#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define fi first
#define se second
#define pb push_back
const int N=50+5;
const int M=1000+5;
const int mod=10000;
int n,m,st,ed,k;
int nf;
struct wer{
	int T,p[6];
}q[25];
struct sdf{
	int p[N][N];
	sdf(){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++)p[i][j]=0;
		}
	}
	sdf operator*(const sdf&x)const{
		sdf tmp;
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				for (int k=1;k<=n;k++){
					tmp.p[i][j]=(tmp.p[i][j]+p[i][k]*x.p[k][j]%mod)%mod;
				}
			}
		}
		return tmp;
	}
}A,B,C,id,mp;
void fst(int x){
	if (!x){
		A=id;return ;
	}
	if (x&1){
		fst(x-1);A=A*C;return ;
	}
	else{
		fst(x/2);A=A*A;return ;
	}
}
int main(){
	freopen ("swamp.in","r",stdin);
	freopen ("swamp.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&st,&ed,&k);st++,ed++;
	for (int i=1;i<=n;i++)id.p[i][i]=1;
	for (int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);x++,y++;
		mp.p[x][y]=mp.p[y][x]=1;
	}
	scanf("%d",&nf);
	for (int i=1;i<=nf;i++){
		int T;scanf("%d",&T);q[i].T=T;
		for (int j=0;j<T;j++)scanf("%d",&q[i].p[j]),q[i].p[j]++;
	}
	C=id;
	for (int i=1;i<=12;i++){
		B=mp;
		for (int j=1;j<=nf;j++){
			int x=q[j].p[i%q[j].T];
			for (int l=1;l<=n;l++){
				B.p[l][x]=0;
			}
		}
		C=C*B;
	}
	int kk=k/12;
	fst(kk);
	for (int i=1;i<=k%12;i++){
		B=mp;
		for (int j=1;j<=nf;j++){
			int x=q[j].p[i%q[j].T];
			for (int l=1;l<=n;l++){
				B.p[l][x]=0;
			}
		}
		A=A*B;
	}
	printf("%d\n",A.p[st][ed]);
	return 0;;
}