Hide
Problem B
Royal Routing
Languages
en
is
A king piece starts at A1 on a normal $8 \times 8$ chessboard. You are given a positive integer $n \leq 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 \leq 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$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
8 |
56 |
| Sample Input 4 | Sample Output 4 |
|---|---|
20 |
897691418 |
