Cho dãy 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 là số là là tạo ra dãy số mới mà các phần tử được tạo ra bằng cách cộng hai số cạnh 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ố ban đầu một phần. Ta nén dãy số đến khi còn một phần tử, phần tử đó là giá trị của dãy số. Ví dụ: ~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

Yêu cầu: Viết chương trình xấu ra giá trị nén của dãy . 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ố ~10^9~.

Input

• Nhập số nguyên ~N~ (~1≤N≤400~) .

Output In ra số dư của phép chia giá trị nén của dãy số cho hay (~10^9~).

Examples

Input1

4

Output1

20

Input2

15

Output2

131072