#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=30,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 POW(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod,y>>=1;}return rt;} int jc[MAXN],ny[MAXN]; int C(int x,int y){ if(x<y)return 0; return jc[x]*ny[y]%Mod*ny[x-y]%Mod; } int n,m,k,d,a[MAXN]; struct matrix{ int p[MAXN][MAXN],x,y; void init(int a,int b){ x=a,y=b; for(int i=1;i<=x;i++){ for(int j=1;j<=y;j++)p[i][j]=1; } } matrix operator *(const matrix&G)const{ matrix res; res.x=x,res.y=G.y; for(int i=1;i<=x;i++){ for(int j=1;j<=G.y;j++){ res.p[i][j]=0; for(int k=1;k<=y;k++){ res.p[i][j]+=p[i][k]*G.p[k][j]%Mod; res.p[i][j]%=Mod; } } } return res; } }G; matrix Pow(matrix x,int y){ matrix res; res.init(1,n); while(y){ if(y&1)res=res*x; x=x*x;y>>=1; } return res; } int p[MAXN],ans; void dfs(int now,int sum){ if(now==k+1){ matrix res;res.x=res.y=n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(p[a[i]]||p[a[j]])res.p[i][j]=0; else res.p[i][j]=G.p[i][j]; } } res=Pow(res,d); int num=0; for(int i=1;i<=n;i++)num=(num+res.p[1][i])%Mod; if(sum&1)ans+=(Mod-num)%Mod; else ans+=num%Mod; ans%=Mod; return; } p[now]=0; dfs(now+1,sum); p[now]=1; dfs(now+1,sum+1); } void slv(){ n=read(),m=read(),k=read(),d=read()-1; for(int i=1;i<=k;i++)a[read()]=i; for(int i=1;i<=m;i++){ int u=read(),v=read(); G.p[u][v]=G.p[v][u]=1; } dfs(1,0); printf("%lld",ans); } signed main(){ jc[0]=ny[0]=1;for(int i=1;i<=MAXN-10;i++)jc[i]=jc[i-1]*i%Mod,ny[i]=POW(jc[i],Mod-2); slv(); return 0; }