时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H需要尽快将情报送回总部，从小H所在的位置到总部之间有很多交叉路口。敌人的探照灯周期性地在一些交叉路扫视，若小H与探照灯出现在某个路口就会被敌人发现，他应到尽量避免这种情况发生。小H每分钟可以沿着一条道路从一个路口走到下一个路口，且不会再任何路口停留。探照灯也是一分钟扫视一个路口，接着下一分钟扫视下一个路口。

　　由于总部首长要在 \(k\) 分钟之后才能回来，所以小H必须要在 \(k\) 分钟后准时向首长汇报。作为规划大师，小H想知道回到总部的路径数目。

【输入格式】

　　第一行是 \(n,m,s,e,k\)，表示交叉口数目为 \(n\)，有 \(m\) 条连接交叉口的道路，小H的出发点在 \(s\)，总部在 \(e\)，首长在 \(k\) 分钟后回来。
接下来的 \(m\) 行，每行包含两个整数 \(x,y\)，表示从 \(x\) 到 \(y\) 有一双向条道路。
第 \(m+2\) 行首先是一个整数 \(t\)，表示探照灯的扫视周期，接下来的 \(t\) 个整数 \(x_1,x_2,…,x_t\)，表示在一个周期内，探照灯扫视的路口。

【输出格式】

　　输出路径种数，因为这个数可能很大，只需要输出除以 10000 的余数。

【输入输出样例】

　Input

6 8 2 6 3
1 3
3 2
2 1
1 6
6 2
2 5
5 4
4 6
3 1 6 2

　Output

2

【数据限制】

　　对于 \(100\%\) 的数据，\(1 ≤ n ≤ 50\)，\(1 ≤ m ≤ \frac{N*(N-1)}{2}\)，\(1 ≤ k ≤ 2000000000\)

【来源】

　　Mr.he**