CSG-CPC
Online Judge

1223 : 毕业季

         Time Limit: 1 Sec     Memory Limit: 256 Mb     Submitted: 1     Solved: 1    

Description

在繁忙的毕业季,又有一群人即将告别校园的朋友们,他们经历了四年的时光,共同度过了青春岁月。小Y作为当年的毕业生之一,小Y想要为自己的大学生活画上一个完美的句号,于是他决定组织一次持续\(d\)天难忘的宿舍毕业旅行。

室友们选定了 \(n\) 个城市作为候选的旅游城市,标记为\(1\) \(\sim\) \(n\),这些城市由\(m\) 条双向道路连接而成,在这\(n\)个城市中,有\(k\)个城市是大家一致同意一定要去的,在宿舍旅途中,必须经过这\(k\) 个城市每个至少一次。

旅游的起点可以是\(1\) \(\sim\) \(n\)中任意一个城市,终点也是可以是任意一个城市,每天可以从当前城市走到有边直接相连的另一城市(但不能停留在当前城市),旅程可以用一个长度为 \(d\) 是数列来表示,第 \(i\)项 为第\(i\)天所在城市(第一项为起点城市)

小Y想知道有多少种旅行方案(也就是有多少个不同的数列,只要有某一天所在的城市不同,就认为这两种方案不同),由于小Y忙于写毕业论文,所以这个任务就交给你了,小Y 只想知道方案数模(\(10^9+9\)) 后的答案。

Input

第一行四个非负整数\(n\)\(m\)\(k\)\(d\)(\(1≤n≤20\),\(1 \le m \le 150\),\(0≤k≤min(n, 7)\), \(1≤d≤10^9\))含义如题。

接下来\(k\)个整数,表示\(k\)个旅行中一定需要经过的城市编号。

接下来 \(m\) 行,每行两个数 \(u_i,v_i\),表示\(u_i\)\(v_i\)之间有一条双向道路,保证没有重边和自环。

Output

输出一行, 旅行方案数取模(\(10^9+9\))后的值

Sample

4 4 2 3
1 2
1 2
2 3
3 1
2 4
10

Hint