E. Knight Paths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A knight stands in the top-left corner of an $$$8 \times 8$$$ chessboard. You can move it at most $$$k$$$ times. Count such possible paths modulo $$$2^{32}$$$.

Formally, count paths of cells $$$(C_1, C_2, \ldots, C_s)$$$ such that $$$1 \leq s \leq k+1$$$ and a knight can move from $$$C_i$$$ to $$$C_{i+1}$$$ for every $$$i$$$.

(A chess knight moves to a square that is two squares away horizontally and one square vertically, or one away horizontally and two vertically.)

Input

An integer $$$k$$$ ($$$0 \leq k \leq 10^9$$$).

Output

Print the answer modulo $$$2^{32} = 4294967296$$$.

Examples
Input
1
Output
3
Input
2
Output
15
Input
6
Output
17231
Note

In the first sample test, a knight can either stay in the initial cell $$$(1, 1)$$$ or move to $$$(2, 3)$$$ or $$$(3, 2)$$$. That's 3 ways in total.