#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+9; const int maxn=27; int n,m,k,d; //Matrix struct Mat{ int M[maxn][maxn]; Mat(){memset(M,0,sizeof(M));} void I(){ for(int i=1;i<=n;i++)M[i][i]=1; } int &operator()(const int i,const int j){ return M[i][j]; } }; Mat operator*(Mat A,Mat B){ Mat ret; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++)ret(i,j)=(ret(i,j)+A(i,k)*B(k,j)%mod)%mod; } } return ret; } inline Mat qpow(Mat A,int k){ Mat ans;ans.I(); while(k){ if(k&1)ans=ans*A; A=A*A; k>>=1; } return ans; } Mat A; int ans; int id[maxn]; struct edge{ int u,v; }ed[maxn<<3]; inline int pc(int x){ return __builtin_popcount(x); } signed main(){ cin>>n>>m>>k>>d; for(int i=1;i<=k;i++){ int t; cin>>t; id[t]=i; } for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; ed[i]=(edge){u,v}; } for(int S=0;S<(1<<k);S++){ Mat ret; for(int i=1;i<=m;i++){ int u=ed[i].u,v=ed[i].v; bool b1=(!id[u])||(S>>(id[u]-1)&1^1); bool b2=(!id[v])||(S>>(id[v]-1)&1^1); if(b1&&b2)ret(u,v)=ret(v,u)=1; } ret=qpow(ret,d-1); int cur=0; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cur=(cur+ret(i,j))%mod; ans=(ans+(pc(S)&1?mod-cur:cur))%mod; } cout<<ans<<endl; }