#include<bits/stdc++.h> #define ll long long #define pc __builtin_popcount using namespace std; bool e[25][25];int n,m,k,d;int mod=1e9+9; struct mat{ int H,W; ll A[25][25]; mat operator*(const mat &b){ mat c; c.H=H;c.W=b.W; for(int i=1;i<=c.H;i++){ for(int j=1;j<=c.W;j++){ c.A[i][j]=0; for(int t=1;t<=W;t++){ c.A[i][j]+=1ll*A[i][t]*b.A[t][j]%mod; }c.A[i][j]%=mod; } }return c; } }; mat I,T,nt; void print(mat tmp){ for(int i=1;i<=tmp.H;i++){ for(int j=1;j<=tmp.W;j++){ cout<<tmp.A[i][j]<<' '; }cout<<endl; } }mat qp(mat a,ll b){ mat x=I; while(b){//print(a); if(b&1) x=x*a; b>>=1;mat tmp=a*a;a=tmp; //print(x);cout<<endl;print(a);cout<<endl; }return x; }void bd(){ I.H=n,I.W=n; T.H=n,T.W=n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ I.A[i][j]=(i==j); T.A[i][j]=e[i][j]; } } } int cd[25]; void slv(){ cin>>n>>m>>k>>d; long long ans=0; for(int i=1;i<=k;i++){ int id;cin>>id; cd[i]=1<<(id-1); }for(int i=1;i<=m;i++){ int u,v;cin>>u>>v;e[u][v]=1,e[v][u]=1; }bd(); for(int i=0;i<(1<<k);i++){ int pf=1,st=0; for(int j=1;j<=k;j++){ if((i&pf)!=0) st|=cd[j]; pf*=2; }mat f;f.H=1,f.W=n; for(int j=1;j<=n;j++) if((st&(1<<(j-1)))==0)f.A[1][j]=1;else f.A[1][j]=0; nt=T; for(int j=1;j<=n;j++){ for(int t=1;t<=n;t++){ if((st&(1<<(j-1)))!=0||((st&(1<<(t-1)))!=0)) nt.A[j][t]=0; } }//print((nt));cout<<endl; //print(qp(nt,3));cout<<endl; f=f*qp(nt,d-1); long long dt=0; for(int j=1;j<=n;j++) dt+=f.A[1][j]/*,cout<<f.A[1][j]<< ' '*/; dt%=mod;//cout<<endl; if(pc(st)%2==1) dt=mod-dt; ans+=dt; //print(nt); //cout<<dt<<endl; } cout<<ans%mod; } int main(){ slv(); }