Giải bài trực tuyến

Cho 1 đồ thị có N đỉnh, M cạnh 2 chiều. 2 đỉnh được nối với nhau nhiều nhất là 1 cạnh.

1 đường đi là 1 chuỗi các đỉnh sao cho các đỉnh kề nhau có cạnh nối với nhau.

1 đường đi đẹp phải thỏa mãn :

- Chuỗi đỉnh có độ dài là D.

- Các đỉnh từ 1 đến K phải xuất hiện ít nhất 1 lần.

Yêu cầu : Tính số đường đi đẹp mod 1000000009.

Giới hạn N<=20, D<=1000000000. K<=7.

Input

- 4 số N,M,K,D

- M dòng mỗi dòng 2 số u,v cho biết có đường đi 2 chiều cạnh nỗi 2 đỉnh u và v

Output

- Số đường đi đẹp mod 1000000009.

Sample input

4 4 2 3

1 2

2 3

3 1

2 4

Sample output

10

#Giải thích

Các đường đi có thể là :

- 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