https://ac.nowcoder.com/acm/contest/76795/D

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb(i) push_back(i)
//#define int long long
#define INF 0x3f3f3f3f
#define oz  998244353
#define endl '\n'
#define N 5010
const int mod = 1e9 + 7;


int p[N], si[N];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
//size[find(b)] += size[find(a)];
//p[find(a)] = find(b);

int n, m, Q, x;
vector<int> g[1000010]; //无向图存领接表
int vis[1000010];
int dis[1000010]; //存i点到x的距离
ll cnt[N];  //存长度为i的路径个数
ll dp[N][N]; //dp(i, j)代表考虑了dis <= i, 且有j个锚点一共有多少种方案

void solve() {
    cin >> n >> m >> Q >> x;

    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    queue<int> q;
    vis[x] = 1;
    q.push(x);

    while (!q.empty()) { // bfs求出所有点到x的路径长度
        auto now = q.front();
        q.pop();

//      vis[now] = 1;
        for (auto to : g[now]) {
            if (vis[to])continue;

            vis[to] = 1;
            dis[to] = dis[now] + 1;
            cnt[dis[to]] ++;

            q.push(to);
        }
    }

    dp[0][0] = 1;

    rep(i, 1, 5000) {
        rep(k, 0, 5000) {
            dp[i][k] = dp[i - 1][k]; //不选dis为i的方案数

            if (k)dp[i][k] = dp[i][k] + dp[i - 1][k - 1] * cnt[i]; //选dis为i的方案数
            dp[i][k] %= mod;
        }
    }

    while (Q --) {
        int k;
        cin >> k;

        cout << dp[5000][k] << endl;
    }

}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
//  cin >> T;
    while (T --)

        solve();

    return 0;
}