题目描述

终于，小明毕业了，他规划进行一次毕业旅行。经过长时间的筛选，小明最终定下来 $n$ 个城市作为旅行的目的地，并将这些城市人为编号为 $1,2,\dots,n$。这些城市由 $m$ 条双向道路连接而成。

小明非常喜欢其中编号为 $1,2,\dots,k$ 的那些城市，在他的旅行中，必须经过 $[1,k]$ 这 $k$ 个城市至少一次。当 $k$ 为 $0$ 时，表示小明不是必须要经过规定的城市。

现在小明会进行为期 $d$ 天的旅行，每一天小明都可以前往一个城市。小明的起点可以是 $1\sim n$ 中任意一个城市，终点也可以是 $1\sim n$ 中的任意一个城市，他每天都可以从一个城市走到另一个有道路直接相连的城市。我们可以将小明的旅行表示成一个长度为 $d$ 的数列，其中数列的第 $i$ 项为小明第 $i$ 天所在的城市（第 $1$ 项作为起点城市）。

• 注意：小明不能连续两天呆在一个城市，即每一天小明必须前往一个有边相连的其他城市。
• 例如，假设一定要去到 $1,2$ 这两个城市，旅行 $3$ 天，那么旅行数列 $\{1,2,1\}$ 是一种合法的方案, 而 $\{1,2,2\}$ 是不合法的，这种方案中小明第 $2$ 天到第 $3$ 天都在城市 $2$。

现在小明想知道有多少种不同的旅行方案，即可以表示成多少个长度为 $d$ 的不同数列，只要有某一天所在的城市不同，就认为这两种方案不同。

小明又将这个问题交给了精通编程的你，现在想知道方案数模 $10^9+9$ 的答案。

输入格式

第一行四个非负整数 $n,m,k,d$，含义如题面所述。

接下来有 $m$ 行，每行两个数 $u,v$，表示 $u$ 和 $v$ 之间有一条双向道路相连。

输出格式

输出一行一个整数，表示方案数模 $10^9+9$ 后的值。

输入输出样例 #1

输入 #1

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

输出 #1

10

说明/提示

【样例解释】

小明必须要去城市 $1,2$ 至少一次，进行 $3$ 天的旅行。通过枚举，可以发现满足要求的不同的旅行序列有：$\{1,2,1\},\{1,2,3\},\{1,2,4\},\{1,3,2\},\{2,1,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\},\{4,2,1\}$，共 $10$ 种不同的方式。

【数据范围】

对于所有数据，不保证图全连通，但保证没有重边和自环。

其中所有数据都满足 $1\le n \le 20, 1 \le m \le \min(150,n*(n-1)/2),0 \le k \le \min(n,7),1\le d \le 10^9$，具体分布如下表所示。