Matrix Exponentiation - Knight Paths

View as PDF

Submit solution


Points: 0.80
Time limit: 1.0s
Memory limit: 256M

Suggester:
Problem source:
Matrix Exponentiation
Problem type
Allowed languages
C, C++, Java, Pascal, Python

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

Please read the guidelines before commenting.


There are no comments at the moment.