冥古之潮
题号：NC267947
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

万物因时潮涌
锚点又在何方
白垩色的王子给了你一张由 n 个点和 m 条无向边构成的联通图（结点编号从 1 至 n，保证不存在重边和自环），每条边的长度均为 1，同时，他又给了你一点 x。
白垩色的王子告诉你图上存在 k 个锚点。记第 i 个锚点所在点的编号为 a_i，记点 a_i 到点 x 的最短距离为 dis_i。他又告诉你，这 k 个锚点的位置满足 dis_1 < dis_2< \dots < dis_k，且对于任意一个锚点 i，都有 dis_i \ne 0。
同时，这个图还满足：记图中一点 i 到点 x 的距离为 Dis_i，保证 \max_{i=1}^n Dis_i \le 5000。
现在白垩色的王子想知道，这 k 个锚点的位置有多少种可能。具体地，我们记这 k 个锚点的位置组成了一个集合 S=\{a_1,a_2,\dots,a_k\}，对于两个集合，如果他们有任意一个元素不一样，我们就认为这两个集合是不一样的。也就是说，你只需要输出合法的不同集合数即可。
一共有 q 组询问，每组询问给出一个 k，你需要求出锚点数量为 k 时的可能位置方案数。
由于答案可能过大，你只需要输出它对 10^9+7 取模的结果。

输入描述:

第一行输入四个整数 n,m,q,x(1\le n,m \le 10^6，1\le q \le 5000,1\le x \le n)，意义如题面所示。
接下来 m 行，每行包含两个整数 u,v(1\le u,v \le n)，表示在 u,v 之间存在一条无向边。
接下来 q 行，每行输入一个整数 k(1\le k \le 5000)，表示锚点的数量。

输出描述:

输出 q 行，第 i 行输出一个整数表示对于第 i 组询问给出的 k，锚点位置的合法方案数，结果对 10^9+7 取模。
示例1

输入

复制 
3 3 2 1
1 2
2 3
3 1
1
2

输出

复制 
2
0

说明

 k=1 时锚点可放在点 2 或 3，k=2 时无法放置。
示例2

输入

复制 
9 10 3 1
1 2
2 7
7 5
5 3
3 6
5 6
1 3
9 8
1 4
4 8
2
3
100

输出

复制 
19
12
0