#include <bits/stdc++.h> #define int long long using namespace std; const int md = 1e9 + 9; int n,m,k,d,cnt,ans; struct edge { int to; int nxt; } e[114514]; int a[114514],b[114514],h[114514]; void add (int u,int v) { cnt++; e[cnt].to = v; e[cnt].nxt = h[u]; h[u] = cnt; } void dfs (int p,int day) { b[p]++; if (day == d) { bool B = 1; for (int i = 1;i <= k;i++) { if (b[a[i]] == 0) { B = 0; } } if (B) { ans++; ans %= md; } b[p]--; return; } for (int i = h[p];i;i = e[i].nxt) { dfs(e[i].to,day + 1); } b[p]--; } signed main () { freopen("loong.in","r",stdin); freopen("loong.out","w",stdout); scanf("%lld %lld %lld %lld",&n,&m,&k,&d); for (int i = 1;i <= k;i++) { scanf("%lld",&a[i]); } for (int i = 1;i <= m;i++) { int u,v; scanf("%lld %lld",&u,&v); add(u,v); add(v,u); } for (int i = 1;i <= n;i++) { dfs(i,1); } ans = (ans + md) % md; printf("%lld",ans); return 0; }