A Walk Around the Main Campus

Time limit1sMemory limit512 MB

Summary

Count closed walks of exactly D minutes from the Information Science Building in a fixed eight-building graph, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Graph, Matrix
Solved: No attempts yet

Problem

The Information Science Building of Soongsil University sits by itself across the road from the rest of the campus. Computer science students therefore call the campus proper the main side and the Information Science Building the CS side. Junyoung is a computer science student, so he is shut up in the Information Science Building and always wants to go over to the main side. One day he decided to take a walk there.

The campus map is below. For this problem, assume the campus has only the eight buildings drawn on it.

Every road between two buildings is two-way, and the adjacency is as follows.

Building	Adjacent buildings
Information Science Building	Computing Building, Mirae Hall
Computing Building	Information Science Building, Sinyang Hall, Mirae Hall
Sinyang Hall	Computing Building, Mirae Hall, Jinri Hall, Hangyeongjik Memorial Hall
Mirae Hall	Information Science Building, Computing Building, Sinyang Hall, Hangyeongjik Memorial Hall
Jinri Hall	Sinyang Hall, Hangyeongjik Memorial Hall, Student Union
Hangyeongjik Memorial Hall	Sinyang Hall, Mirae Hall, Jinri Hall, Hyeongnam Engineering Building
Student Union	Jinri Hall, Hyeongnam Engineering Building
Hyeongnam Engineering Building	Hangyeongjik Memorial Hall, Student Union

Moving from one building to an adjacent building takes 1 minute. Junyoung never stops on a road or inside a building while walking. He has a lot to do, so he walks for exactly $D$ minutes: he starts at the Information Science Building and must be back at the Information Science Building at the moment $D$ minutes have passed. He may pass through the same building several times and use the same road several times.

Two routes are different if the sequence of visited buildings differs at any position. Count the possible routes.

Input

The first line contains the integer $D$ . ( $1 \le D \le 100{,}000$ )

Output

Print the number of possible routes modulo $1{,}000{,}000{,}007$ .

Examples4

Example 1
Input
```
10
```
Expected output
```
9857
```
Example 2
Input
```
1
```
Expected output
```
0
```
Example 3
Input
```
2
```
Expected output
```
2
```
Example 4
Input
```
3
```
Expected output
```
2
```