#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=27; const int mod=1e9+9; int n,m,k,d; vector<int> E[maxn]; int vis[maxn]; int IM[maxn]; int id[maxn]; int cnt=0; void dfs(int u,int dis){ if(dis==d){ bool b=1; for(int i=0;i<k;i++){ if(!vis[IM[i]]){ b=0; break; } } if(b)cnt++; cnt%=mod; return; } for(auto v:E[u]){ vis[v]++; dfs(v,dis+1); vis[v]--; } } void BF(){ for(int i=1;i<=n;i++){ vis[i]++; dfs(i,1); vis[i]--; } cout<<cnt<<endl; } const int D34=2e3+7; const int MS=(1<<7)+7; int f[D34][maxn][MS]; void Sub34(){ for(int i=1;i<=n;i++){ if(id[i]!=10086)f[1][i][1<<id[i]]=1; else f[1][i][0]=1; } for(int dis=2;dis<=d;dis++){ for(int i=1;i<=n;i++){ for(int S=0;S<(1<<k);S++){ for(auto v:E[i]){ if(id[v]!=10086)f[dis][v][S|(1<<id[v])]=(f[dis][v][S|(1<<id[v])]+f[dis-1][i][S])%mod; else f[dis][v][S]=(f[dis][v][S]+f[dis-1][i][S])%mod; } } } } int ans=0; for(int i=1;i<=n;i++)ans=(ans+f[d][i][(1<<k)-1])%mod; cout<<ans<<endl; } signed main(){ cin>>n>>m>>k>>d; for(int i=1;i<=n;i++)id[i]=10086; for(int i=0;i<k;i++)cin>>IM[i],id[IM[i]]=i; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; E[u].push_back(v); E[v].push_back(u); } // if(d<=5){ // BF(); // return 0; // } if(d<=2000){ Sub34(); return 0; } }