Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
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.