Cho một số tự nhiên ~N~, ta có một dãy số ~A~ gồm các số tự nhiên từ 1 đến ~N~.

Phép nén dãy số là tạo ra dãy số mới mà các phần tử được tạo ra bằng cách lần lượt cộng hai số cạnh nhau của dãy số ban đầu. Mỗi lần nén dãy số, dãy số mới sẽ ít hơn dãy số trước một phần tử. Ta nén dãy số đến khi còn một phần tử, phần tử đó là giá trị nén của dãy số.

Ví dụ: với ~N = 4~ ta có kết quả cuối cùng là số ~20~:

Dãy ban đầu: ~1\ 2\ 3\ 4~
Nén lần 1: ~3\ 5\ 7~
Nén lần 2: ~8\ 12~
Nén lần 3: ~20~

Viết chương trình xuất ra giá trị nén của dãy số. Vì kết quả có thể rất lớn, nên chỉ cần xuất ra số dư của phép chia giá trị nén của dãy số cho ~1000000000~ (hay ~10^9~).

INPUT

Nhập từ bàn phím giá trị của số ~N~ ~(1 < N < 400)~.

OUTPUT

Xuất ra màn hình kết quả là số dư của phép chia giá trị nén của dãy số cho ~1000000000~ (hay ~10^9~).

SAMPLE INPUT 1

4

SAMPLE OUTPUT 1

20

SAMPLE INPUT 2

15

SAMPLE OUTPUT 2

131072