#include<bits/stdc++.h>
#define N 57
#define mod 10000
using namespace std;
struct matrix
{
    int A[N][N];
};
matrix ans, sum[13], g, vis;
matrix mul(matrix a, matrix b, int n)
{
    matrix r;
    memset(r.A, 0, sizeof(r.A));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            for(int k = 0; k < n; k++)
            {
                r.A[i][j] += a.A[i][k]*b.A[k][j];
            }
            r.A[i][j] %= mod;
        }
    }
    return r;
}
int main()
{
    int n, k, s, e, m, nf, mk;
    freopen("swamp.in","r",stdin);
	freopen("swamp.out","w",stdout);
    scanf("%d%d%d%d%d", &n, &m, &s, &e, &k);
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            ans.A[i][j] = (i==j);
            vis.A[i][j] = 0;
            sum[0].A[i][j] = (i==j);
            for(int l = 1; l < 13; l++)
            {
                sum[l].A[i][j] = 0;
            }
        }
    }
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g.A[x][y] = g.A[y][x] = 1;
    }
    scanf("%d", &nf);
    for(int i = 1; i <= nf; i++)
    {
        int t;
        scanf("%d", &t);
        for(int j = 0; j < t; j++)
        {
            int p, h = j;
            scanf("%d", &p);
            while(h<=12)
            {
                vis.A[p][h] = 1;
                h += t;
            }
        }
    }
	for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(!vis.A[i][0]&&!vis.A[j][1])
            {
                sum[1].A[i][j] = g.A[i][j];
            }
        }
    }
    for(int i = 1; i < 12; i++)
    {
        for(int j = 0; j < n; j++)
        {
            for(int l = 0; l < n; l++)
            {
                for(int p = 0; p < n; p++)
                {
                    if(!vis.A[l][i+1])
                    {
                        sum[i+1].A[j][l] += sum[i].A[j][p]*g.A[p][l];
                    }
                }
                sum[i+1].A[j][l] %= mod;
            }
        }
    }
    g = sum[12];
    mk = k%12;
    k -= mk;
    k /= 12;
    while(k)
    {
        if(k&1)
        {
            ans = mul(ans, g, n);
        }
        g = mul(g, g, n);
        k >>= 1;
    }
    ans = mul(ans, sum[mk], n);
    printf("%d\n", ans.A[s][e]);
    return 0;
}