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.)
An integer $$$k$$$ ($$$0 \leq k \leq 10^9$$$).
Print the answer modulo $$$2^{32} = 4294967296$$$.
1
3
2
15
6
17231
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.