RT，挂成30，自己看没啥问题啊/fad

#include <bits/stdc++.h>
#define min(x,y) ((y)^(((x)^(y))&(-((x)<(y)))))
#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))
using namespace std;
struct control{
    int ct,val;
    control(int Ct,int Val=-1):ct(Ct),val(Val){}
    inline control operator()(int Val){
        return control(ct,Val);
    }
}_endl(0),_prs(1),_setprecision(2);
struct FastIO{
    #define IOSIZE 1000000
    #define endl "\n"
    char in[IOSIZE],*p,*pp,out[IOSIZE],*q,*qq,ch[20],*t,b,K,prs;
    FastIO():p(in),pp(in),q(out),qq(out+IOSIZE),t(ch),b(1),K(6){}
    ~FastIO(){fwrite(out,1,q-out,stdout);}
    inline char getch(){
        return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?b=0,EOF:*p++;
    }
    inline void putch(char x){
        q==qq&&(fwrite(out,1,q-out,stdout),q=out),*q++=x;
    }
    inline void puts(const char str[]){fwrite(out,1,q-out,stdout),fwrite(str,1,strlen(str),stdout),q=out;}
    inline void getline(string& s){
        s="";
        for(register char ch;(ch=getch())!='\n'&&b;)s+=ch;
    }
    #define indef(T) inline FastIO& operator>>(T& x){\
        x=0;register char f=0,ch;\
        while(!isdigit(ch=getch())&&b)f|=ch=='-';\
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getch();\
        return x=f?-x:x,*this;\
    }
    indef(int)
    indef(long long)
    indef(unsigned long long)
    inline FastIO& operator>>(char& ch){return ch=getch(),*this;}
    inline FastIO& operator>>(string& s){
        s="";register char ch;
        while(isspace(ch=getch())&&b);
        while(!isspace(ch)&&b)s+=ch,ch=getch();
        return *this;
    }
    inline FastIO& operator>>(double& x){
        x=0;register char f=0,ch;
        double d=0.1;
        while(!isdigit(ch=getch())&&b)f|=(ch=='-');
        while(isdigit(ch))x=x*10+(ch^48),ch=getch();
        if(ch=='.')while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1;
        return x=f?-x:x,*this;
    }
    #define outdef(_T) inline FastIO& operator<<(_T x){\
        !x&&(putch('0'),0),x<0&&(putch('-'),x=-x);\
        while(x)*t++=x%10+48,x/=10;\
        while(t!=ch)*q++=*--t;\
        return *this;\
    }
    outdef(int)
    outdef(long long)
    outdef(unsigned long long)
    inline FastIO& operator<<(char ch){return putch(ch),*this;}
    inline FastIO& operator<<(const char str[]){return puts(str),*this;}
    inline FastIO& operator<<(const string& s){return puts(s.c_str()),*this;}
    inline FastIO& operator<<(double x){
        register int k=0;
        this->operator<<(int(x));
        putch('.');
        x-=int(x);
        prs&&(x+=5*pow(10,-K-1));
        while(k<K)putch(int(x*=10)^48),x-=int(x),++k;
        return *this;
    }
    inline FastIO& operator<<(const control& cl){
        switch(cl.ct){
            case 0:putch('\n');break;
            case 1:prs=cl.val;break;
            case 2:K=cl.val;break;
        }
    }
    inline operator bool(){return b;}
}io;
struct Matrix{
    #define N 15
    #define M 15
    long long n,m,d[52][52];
    auto& operator[](std::size_t p) { return d[p]; }
    Matrix(){n=0,m=0;memset(d,0,sizeof(d));}
    inline Matrix operator*(Matrix b){
        Matrix c;c.n=n,c.m=b.m;
        for(register int i=1;i<=n;i++)
        for(register int j=1;j<=b.m;j++){
        c.d[i][j]=0;
        for(register int k=1;k<=m;k++)c.d[i][j]=(c.d[i][j]+1ll*d[i][k]*b.d[k][j])%10000;
        }
        return c;
    }
    inline Matrix operator*=(Matrix b){
        Matrix c;c.n=n,c.m=m,memcpy(c.d,d,sizeof(d)),c=c*b;
        n=c.n,m=c.m,memcpy(d,c.d,sizeof(c.d));
        return c;
    }
    inline void E(int _n){n=m=_n;for(register int i=1;i<=n;i++)d[i][i]=1;}
    inline Matrix pow(int b){
        Matrix a,res;a.n=n,a.m=m,memcpy(a.d,d,sizeof(d));
        memset(res.d,0,sizeof(res.d));res.n=res.m=a.n;
        for(register int i=1;i<=a.n;i++)res.d[i][i]=1;
        while(b){
            if(b&1)res*=a;
            a*=a,b>>=1;
        }
        return res;
    }
}g[15];
int n,m,t,p,nfish,s,e,k,u,v;
int main(){
    #ifndef ONLINE_JUDGE
        #define FILE_OUTPUT
        #ifdef FILE_OUTPUT
        freopen("P2579.in","r",stdin);
        freopen("P2579.out","w",stdout);
        #endif
        long long c1=clock();
    #endif
    io>>n>>m>>s>>e>>k;s++,e++;
    for(register int i=1;i<=12;i++)g[i].n=g[i].m=n;
    while(m--){
        io>>u>>v;u++,v++;
        // io<<u<<' '<<v<<endl;
        for(register int i=1;i<=12;i++)g[i][u][v]=g[i][v][u]=1;
    }
    /*for(register int i=1;i<=3;i++,io<<i<<endl)
    for(register int j=1;j<=n;j++,io<<endl)
    for(register int k=1;k<=n;k++)io<<g[1][j][k]<<' ';*/
    io>>nfish;
    while(nfish--){
        io>>t;
        for(register int i=0;i<t;i++){
            io>>p;p++;
            for(register int j=i;j<=12;j+=t)
            for(register int k=1;k<=n;k++)g[j][k][p]=0;
        }
    }
    /*for(register int i=1;i<=3;i++,io<<i<<endl)
    for(register int j=1;j<=n;j++,io<<endl)
    for(register int k=1;k<=n;k++)io<<g[1][j][k]<<' ';*/
    g[13].E(n);
    if(k<=12){
        for(register int i=1;i<=k;i++){
            g[13]*=g[i];
            // io<<i<<endl;
            // for(register int j=1;j<=n;j++,io<<endl)
            // for(register int z=1;z<=n;z++)io<<g[13][j][z];
        }
        io<<g[13][s][e];
        return 0;
    }else{
        for(register int i=1;i<=12;i++)g[13]*=g[i];
        g[13].pow(k/12);
        for(register int i=1;i<=k%12;i++)g[13]*=g[i];
    }
    io<<g[13][s][e];
    #ifndef ONLINE_JUDGE
        //#define DEBUG
        #ifdef DEBUG
            freopen("CON","w",stdout);
        #endif
        puts("\n--------------------------------");
        printf("Process exited after %g seconds with return value 0\n",(clock()-c1)/1000.0);
        #ifdef DEBUG
            system("pause");
        #endif
    #endif
    return 0;
}