본대 산책 2

숭실대학교 정보과학관은 캠퍼스에서 길 하나를 건너야 닿는 곳에 떨어져 있다. 그래서 컴퓨터학부 학생들은 캠퍼스 쪽을 '본대', 정보과학관 쪽을 '정보대'라고 부른다. 준영이도 컴퓨터학부 학생이라 하루 종일 정보과학관에 박혀 있고, 꽃이 활짝 핀 본대를 늘 선망한다. 어느 날 준영이는 본대를 산책하기로 마음먹었다. 캠퍼스 지도는 아래와 같다.

편의상 이 문제에는 지도에 있는 건물 8개와 그 사이를 잇는 길만 있다고 가정한다. 건물에 1번부터 8번까지 번호를 붙이면 다음과 같다.

길로 바로 이어진 건물 쌍은 다음 12개다.

$(1, 2)$, $(1, 3)$, $(2, 3)$, $(2, 4)$, $(3, 4)$, $(3, 6)$, $(4, 5)$, $(4, 6)$, $(5, 6)$, $(5, 7)$, $(6, 8)$, $(7, 8)$

바로 이어진 두 건물 사이를 옮겨 가는 데 1분이 걸린다. 준영이는 산책하는 동안 길이나 건물에 멈춰 서서 머무르지 않는다. 이미 지나간 건물이나 길은 몇 번이든 다시 지나갈 수 있다.

준영이는 할 일이 많아서 딱 $D$분만 산책한다. 즉 1번 정보과학관에서 출발해 산책을 시작한 지 $D$분이 되는 순간 다시 1번 정보과학관에 도착해야 한다. 지나간 건물의 순서가 한 곳이라도 다르면 서로 다른 경로로 센다. 가능한 경로의 수를 구하자.

첫째 줄에 정수 $D$가 주어진다. ($1 \le D \le 10^9$)

가능한 경로의 수를 $10^9 + 7$로 나눈 나머지를 첫째 줄에 출력한다.