Submit solution
Points:
0.80
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Suggester:
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Một quân mã được đặt ở ô trái trên của bàn cờ kích thước ~8 \times 8~. Bạn được phép di chuyển quân mã đó tối đa ~k~ lần. Hãy đếm số đường đi có thể có với quân mã đó và in ra kết quả dưới dạng modulo cho ~2^{32}~.
Cụ thể hơn, một đường đi là một tập các ô ~(C_1, C_2,..., C_s)~ sao cho ~1 \le s \le k + 1~ và quân mã có thể đi từ ô ~C_i~ đến ô ~C_{i+1}~ với mọi ~i~.
(Một nước đi của quân mã trong bàn cờ vua có dạng ~1~ ô vuông theo chiều ngang và ~2~ ô vuông theo chiều dọc hoặc ~2~ ô vuông theo chiều ngang và ~1~ ô vuông theo chiều dọc)
Input
Số nguyên ~k~ ~(0 \le k \le 10^9)~
Output
In ra kết quả dưới dạng modulo cho ~2^{32} = 4294967296 ~
Sample 1
Input
1
Output
3
Sample 2
Input
2
Output
15
Sample 3
Input
6
Output
17231
Giải thích Sample 1
Quân mã có thể đứng nguyên ở ô ~(1, 1)~ hoặc có thể di chuyển tới các ô ~(2, 3)~ hoặc ~(3, 2)~. Vậy kết quả là ~3~.
Comments