Cho số nguyên dương \(n\), ta có dãy \(a\) gồm các số nguyê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 \(2\) 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 trước \(1\) phần tử. Ta nén dãy số cho đến khi chỉ còn \(1\) phần tử, phần tử đó là giá trị nén của dãy số. Yêu cầu: in 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 in ra số dư của phép chia giá trị nén của dãy số cho \(1000000000 (10^9)\).

Hình trên là ví dụ các phép nén dãy trong trường hợp \(n = 4\), ta có kết quả cuối cùng là \(20\)

Input

• Số \(n\) \((0 < n \le 10^{18})\).

Output

• Giá trị nén theo modulo \(10^9\).

Examples

4    

20