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~.