본대 산책

숭실대학교 정보과학관은 캠퍼스 길 건너편에 따로 떨어져 있다. 그래서 컴퓨터학부 학생은 캠퍼스를 '본대', 정보과학관을 '정보대'라고 부른다. 준영이도 컴퓨터학부 소속이라 정보과학관에만 박혀 있고, 늘 본대에 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 했다.

캠퍼스 지도는 다음과 같다. 문제에서는 지도에 그려진 건물 8개만 있다고 가정한다.

건물 사이를 잇는 길은 모두 양방향이고, 인접 관계는 다음과 같다.

한 건물에서 인접한 다른 건물로 이동하는 데 1분이 걸린다. 준영이는 산책 도중에 길이나 건물에서 한 번도 멈추지 않는다. 준영이는 할 일이 많아서 딱 $D$분만 산책한다. 즉 정보과학관에서 출발해 산책을 시작한 지 $D$분이 되는 순간 다시 정보과학관에 도착해야 한다. 같은 건물을 여러 번 지나가도 되고 같은 길을 여러 번 지나가도 된다.

방문한 건물의 순서가 한 곳이라도 다르면 서로 다른 경로다. 가능한 경로의 수를 구하자.

첫째 줄에 정수 $D$가 주어진다. ($1 \le D \le 100{,}000$)

가능한 경로의 수를 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다.