#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define m_p make_pair #define p1 first #define p2 second using namespace std; typedef long long ll; const int maxn=1e6+10,mod=1e9+9; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,K,D,tag[maxn]; bool ban[maxn]; vector<int>v[maxn]; struct mat { int t[35][35],n,m; mat(){memset(t,0,sizeof(t));} void init(){up(i,1,n)t[i][i]=1;} }; mat operator*(mat a,mat b){ mat c;c.n=a.n,c.m=b.m; up(i,1,a.n)up(j,1,a.m)up(k,1,b.m)(c.t[i][k]+=a.t[i][j]*1ll*b.t[j][k]%mod)%=mod; return c; }mat qpow(mat a,int b){ mat res;res.n=res.m=a.n;res.init(); while(b){ if(b&1)res=res*a; a=a*a;b>>=1; }return res; } int ppc(int x){ int res=0; while(x)res+=x&1,x>>=1; return res; } void slv(){ n=read(),m=read(),K=read(),D=read(); up(i,1,K)tag[read()]=i; while(m--){int x=read(),y=read();v[x].p_b(y),v[y].p_b(x);} int res=0; up(I,0,(1<<K)-1){ mat base,mul; base.n=1,base.m=n; up(i,1,n)ban[i]=((tag[i]&&((I>>(tag[i]-1))&1))?1:0); up(i,1,n)if(!ban[i])base.t[1][i]=1; mul.n=mul.m=n; up(i,1,n)if(!ban[i])for(int x:v[i])if(!ban[x])mul.t[i][x]=1; base=base*qpow(mul,D-1); int ct=0;up(i,1,n)(ct+=base.t[1][i])%=mod; if(ppc(I)&1)res=(res+mod-ct)%mod; else (res+=ct)%=mod; } cout<<res; }int main(){ slv(); fclose(stdin); fclose(stdout); return 0; }