406977: GYM102644 E Knight Paths
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
E. Knight Pathstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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.)
InputAn integer $$$k$$$ ($$$0 \leq k \leq 10^9$$$).
OutputPrint the answer modulo $$$2^{32} = 4294967296$$$.
ExamplesInput1Output
3Input
2Output
15Input
6Output
17231Note
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.