#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v const int MAXN=2010,N=25,Mod=1000000009; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,m,k,d,a[MAXN],f[MAXN][N][1<<7]; string ejz(int x){ string s=""; for(int i=0;i<k;i++){ if(x&(1<<i))s+="1"; else s+="0"; } return s; } int tot; int dfs(int now,int u,int s){ if(~a[u])s|=1<<a[u]; if(now==d){ if(s==(1<<k)-1)return 1; else return 0; } if(~f[now][u][s])return f[now][u][s]; // tot++; // cout<<now<<" "<<u<<" "<<ejz(s)<<endl; // if(tot>=245000)exit(0); f[now][u][s]=0; for(inx(u)){ f[now][u][s]=(f[now][u][s]+dfs(now+1,v,s))%Mod; } return f[now][u][s]; } void slv(){ n=read(),m=read(),k=read(),d=read(); for(int i=1;i<=n;i++)a[i]=-1; for(int i=0;i<k;i++){ int tmp=read(); a[tmp]=i; } for(int i=1;i<=m;i++){ int u=read(),v=read(); add_side(u,v); } memset(f,-1,sizeof(f)); int ans=0; for(int i=1;i<=n;i++){ ans+=dfs(1,i,0); ans%=Mod; } printf("%lld",ans); } signed main(){ slv(); return 0; }