#include<iostream> #include<cstring> #include<ctime> #define timeMS (clock()*1000/CLOCKS_PER_SEC) using namespace std; #define int long long const int N=23,M=160,P=1000000009; struct matrix{ int a[N][N],n,m; inline matrix(){memset(a,0,sizeof(a));n=m=0;} inline matrix(int n_,int m_){memset(a,0,sizeof(a));n=n_,m=m_;} inline int* operator[](int i){return a[i];} inline matrix operator*(matrix&B){ matrix C(n,B.m); for(int i=1;i<=n;i++){ for(int j=1;j<=B.m;j++){ for(int k=1;k<=m;k++)C[i][j]=(C[i][j]+a[i][k]*B[k][j])%P; } } return C; } inline void unit(){for(int i=1;i<=n;i++)a[i][i]=1;} }; inline matrix fpow(matrix A,int b){ matrix C(A.n,A.m);C.unit(); for(;b;b>>=1,A=A*A)if(b&1)C=C*A; return C; } int n,m,k,d; using pii=pair<int,int>; pii e[M]; int id[N]; inline void init(){ cin>>n>>m>>k>>d; d--; for(int i=1;i<=k;i++){ int x;cin>>x; id[x]=i; } for(int i=1;i<=m;i++)cin>>e[i].first>>e[i].second; } inline int solve(int sta){ matrix A(n,n); for(int i=1;i<=m;i++){ int u=e[i].first,v=e[i].second; if(id[u]&&(sta&(1<<(id[u]-1))))continue; if(id[v]&&(sta&(1<<(id[v]-1))))continue; A[u][v]=A[v][u]=1; } A=fpow(A,d); matrix B(1,n); for(int i=1;i<=n;i++){ if(id[i]&&(sta&(1<<(id[i]-1))))continue; B[1][i]=1; } B=B*A; int ans=0; for(int i=1;i<=n;i++)ans=(ans+B[1][i])%P; return ans; } inline int pop(int x){ int cnt=0; while(x)cnt++,x-=x&-x; return cnt; } signed main(){ //freopen("loong.in","r",stdin); //freopen("loong.out","w",stdout); init(); int ans=0; for(int i=0;i<(1<<k);i++){ if(pop(i)&1)ans=(ans-solve(i))%P; else ans=(ans+solve(i))%P; } cout<<(ans+P)%P; // cerr<<timeMS; return 0; }