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)

Dữ liệu vào

• Số nguyên \(k\) \((0 \le k \le 10^9)\)

Dữ liệu ra

• In ra kết quả dưới dạng modulo cho \(2^{32} = 4294967296\)

Input 1

1

Output 1

3

Input 2

2

Output 2

15

Input 3

3

Output 3

79