본대 산책 3

숭실대학교 정보과학관은 캠퍼스에서 길 건너편에 떨어져 있다. 그래서 컴퓨터학부 학생은 캠퍼스를 '본대', 정보과학관을 '정보대'라고 부른다. 준영이도 컴퓨터학부 학생이라 정보대에 박혀 지내면서 꽃이 활짝 핀 본대를 늘 부러워한다. 어느 날 준영이는 본대를 산책하기로 했다.

캠퍼스 지도에는 건물 $n$개가 있고, 인접한 두 건물을 잇는 도로 $m$개가 있다. 도로 하나를 지나 인접한 건물로 가는 데 1분이 걸린다. 준영이는 산책하는 동안 도로에서도 건물에서도 멈춰 머무르지 않는다. 즉 1분마다 도로 하나를 지나 다른 건물로 반드시 이동한다.

준영이는 할 일이 많아서 딱 $D$분만 산책한다. 산책을 시작한 지 $D$분이 되는 순간에 정보대에 도착해 있어야 한다. 정보대는 1번 건물이고, 준영이는 0분에 정보대에 있다. 가능한 경로의 수를 구하여라. 같은 건물과 같은 도로를 여러 번 지나도 되고, 지나는 순서가 다르면 서로 다른 경로로 센다.

첫째 줄에 건물의 수 $n$과 도로의 수 $m$이 주어진다. ($1 \le n \le 50$, $0 \le m \le 1000$)

다음 $m$개 줄에는 도로가 잇는 두 건물의 번호 $a$와 $b$가 주어진다. ($1 \le a, b \le n$, $a \ne b$) 같은 두 건물을 잇는 도로는 한 번만 주어진다.

마지막 줄에 산책 시간 $D$가 분 단위로 주어진다. ($1 \le D \le 10^9$)

가능한 경로의 수를 $1000000007$로 나눈 나머지를 출력한다.