#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 29, M = 159, Mod = 1e9 + 9; struct mat { int n, m, a[N][N]; void clear() {memset(a, 0, sizeof(a));} void init(int nn) { n = m = nn; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = (i == j); } } } } mt; mat operator * (const mat &x, const mat &y) { mat res; res.n = x.n, res.m = y.m; for (int i = 0; i < x.n; i++) { for (int j = 0; j < y.m; j++) { res.a[i][j] = 0; for (int k = 0; k < x.m; k++) { res.a[i][j] = (res.a[i][j] + 1ll * x.a[i][k] * y.a[k][j]) % Mod; } } } return res; } mat fpow(mat a, int b) { mat res; res.init(a.n); while (b) { if (b & 1) res = res * a; a = a * a, b >>= 1; } return res; } struct Edge { int u, v; } E[M]; int n, m, K, d, id[9], vis[N], ans; signed main() { scanf("%d%d%d%d", &n, &m, &K, &d); for (int i = 0; i < K; i++) scanf("%d", &id[i]); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); E[i].u = u, E[i].v = v; } mt.n = mt.m = n; for (int i = 0; i < (1 << K); i++) { mt.clear(); memset(vis, 0, sizeof(vis)); for (int j = 0; j < K; j++) { if (i & (1 << j)) vis[id[j]] = 1; } for (int j = 1; j <= m; j++) { int u = E[j].u, v = E[j].v; if (vis[u] || vis[v]) continue; mt.a[u - 1][v - 1] = mt.a[v - 1][u - 1] = 1; } mt = fpow(mt, d - 1); int sum = 0; for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { (sum += mt.a[j][k]) %= Mod; } } ans = (__builtin_popcount(i) & 1 ? (ans - sum + Mod) % Mod : (ans + sum) % Mod); } printf("%d\n", ans); return 0; }