旅行没有商问题
题号：NC212207
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

我的歌曲只好向陌生的众人倾诉，
他们即使喝彩也会令我心伤，
当年赏识过我的歌诗的知音，
纵然在世亦不知向何方飘零。
                            ——歌德《浮士德》
剧情版题面：（温馨提示：赶时间的话，简化版见下面）
然而出题人可没工夫读歌德，出题人忙得很，他天天都要照顾女友（我可没说是本题出题人）
他现在又在计划寒假带着女友去旅行了，他们决定旅游d天，有n个可选城市（分别编号为1,2,3...n），其中有k个是出题人想去的城市（而对于出题人的女友，出门旅游=逛吃逛吃，所以她并不介意去哪）
在这d天中，他们每天都要一起待在一个城市，由于出题人喜欢赶路，他们不会在连续两天待在同一个城市，但可以在一个城市旅游若干天。
他们可以选择任意一个城市作为旅行的出发地和结束地。
当且仅当两座城市之间修筑有公路（任意两座城市之间不会修筑两条及以上的公路，一座城市不会修筑与自己相连的公路）时，他们可以从一座城市前往另一座城市。
出题人可爱的女友答应陪他在所有k个想去的城市旅游，所以合法的旅游方案中k个出题人想去的城市必须全部经过（经过至少一次，多次不限9）
出题人太忙了，所以他想让你帮他求出全部合法方案数对109+7取余的结果（就是方案数除以109+7的余数）
简化题面：

给出n个点，m条边的无向图。满足无重边、自环，不保证连通。某人在图上依次访问d个节点（即所经过的所有节点构成的序列长度为d）。n个点中有k个点必须至少经过一次。起点、终点任选。求满足条件的方案数对109+7取模的值

输入描述:

第一行四个整数n，m，d，k，分别表示可选城市数量（图上点数），公路总数（无向边边数），旅游天数（访问节点个数），出题人想去的城市数量（必经节点个数）
第二行k个整数，表示出题人想去的各个城市的编号（各必经节点编号）
第三行到第m+2行，每行两个整数x，y，表示编号为x，y的城市之间修筑有一条公路（表示x，y两点间存在一条无向边）

输出描述:

输出一个整数表示答案
示例1

输入

复制 
4 5 4 2
1 2
1 2
1 3
2 3
2 4
3 4

输出

复制 
36

说明

合法方案（举例）：
3-1-2-4
3-1-2-3
2-3-1-3
非法方案（举例）：
4-1-2-3（4,1之间不存在边）
3-4-2-3（必经点1未被经过）

备注:

对于30%的数据，满足n<=5，d<=10
对于60%的数据，满足n<=5，d<=1000
对于另外20%的数据，满足k=0
对于100%的数据，满足n<=20，k<=7，d<=109