Walk on the Main Campus 2

The Information Science Building of Soongsil University sits across the road from the rest of the campus. Computer science students therefore call the main campus side "bondae" and the Information Science Building side "jeongbodae". Junyoung is a computer science student, so he spends all day inside the Information Science Building and envies the main campus, where the flowers are in full bloom. One day he decides to take a walk there. The campus map is below.

For this problem, assume the campus holds only the 8 buildings on the map and the roads between them. Number the buildings from 1 to 8.

The following 12 pairs of buildings are joined by a road.

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

Moving between two directly joined buildings takes 1 minute. Junyoung never stops on a road or inside a building during the walk. He may pass through a building or a road he already used any number of times.

Junyoung has a lot of work to do, so he walks for exactly $D$ minutes. He starts at building 1, the Information Science Building, and must arrive back at building 1 the moment $D$ minutes have passed. Two routes count as different when the sequence of buildings differs in at least one position. Count the possible routes.

The first line holds an integer $D$. ($1 \le D \le 10^9$)

Print the number of possible routes modulo $10^9 + 7$ on the first line.