406977: GYM102644 E Knight Paths

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.