Problem B
Royal Routing

A king piece starts at A1 on a normal $8\times 8$ chessboard. You are given a positive integer $n\le {10}^{18}$. How many ways are there for the king to make it to H8 in exactly $n$ steps? One step is one move for the king piece using normal chess rules. That is, one step horizontally, vertically or diagonally.

Input

The first and only line of input contains a positive integer $n\le {10}^{18}$.

Output

Print the number of ways there are for the king to go from A1 to H8 in exactly $n$ steps. This number might be very large so print the answer modulo ${10}^9+7$.

6

0

7

1

8

56

20

897691418