#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second const int M=1e9+9; struct mat{ int n,m; int T[21][21]; mat(){memset(T,0,sizeof(T));} friend mat operator *(const mat A,const mat B){ mat C; C.n=A.n,C.m=A.m; assert(A.m==B.n); for(int i=1;i<=A.n;i++) for(int k=1;k<=A.m;k++) if(A.T[i][k]) for(int j=1;j<=B.m;j++) C.T[i][j]=(C.T[i][j]+A.T[i][k]*B.T[k][j])%M; return C; } }; bool ok[31]; int p[21]; int u[210],v[210],n,m,k,d; inline void add(int &x,int y){ x+=y; if(x>=M)x-=M; } inline mat UN(int n){ mat C; C.n=C.m=n; for(int i=1;i<=n;i++) C.T[i][i]=1; return C; } inline mat QP(mat a,int x){ mat res=UN(a.n); while(x){ if(x&1)res=res*a; a=a*a; x>>=1; } return res; } inline int calc(int S){ for(int i=1;i<=n;i++)ok[i]=1; for(int i=0;i<k;i++) if(!((S>>i)&1))ok[p[i+1]]=0; mat tmp; tmp.n=tmp.m=n; // cerr<<S<<endl; // for(int i=1;i<=n;i++) // cerr<<ok[i]; // cerr<<endl; for(int i=1;i<=m;i++) if(ok[u[i]]&&ok[v[i]])tmp.T[u[i]][v[i]]=tmp.T[v[i]][u[i]]=1; // for(int i=1;i<=n;i++,cerr<<endl) // for(int j=1;j<=n;j++) // cerr<<tmp.T[i][j]<<" "; // cerr<<endl; // cerr<<tmp.n<<" "<<tmp.m<<endl; mat st; st.n=1,st.m=n; for(int i=1;i<=n;i++) st.T[1][i]=ok[i]; st=st*QP(tmp,d); // for(int i=1;i<=n;i++,cerr<<endl) // for(int j=1;j<=n;j++) // cerr<<QP(tmp,d).T[i][j]<<" "; // cerr<<endl; int res=0; for(int i=1;i<=n;i++) add(res,st.T[1][i]); // cerr<<S<<" "<<res<<endl; return res; } inline int ppc(int x){return __builtin_popcount(x);} signed main(){ ios::sync_with_stdio(0); // freopen("loong.in","r",stdin); // freopen("loong.out","w",stdout); cin>>n>>m>>k>>d; d--; for(int i=1;i<=k;i++) cin>>p[i]; for(int i=1;i<=m;i++) cin>>u[i]>>v[i]; int T=(1<<k)-1; int res=0; for(int S=0;S<=T;S++) if((k-ppc(S))%2==0)add(res,calc(S)); else add(res,M-calc(S)); cout<<res<<endl; fflush(stdout); cout.flush(); return 0; }