Giải bài trực tuyến

Trong toán học, tam giác Pascal là một mảng tam giác của hệ số nhị thức trong tam giác. Thuật toán được đặt theo tên của nhà toán học Pháp nổi tiếng Blaise Pascal

Trong tam giác số này, bắt đầu từ hàng thứ hai, mỗi số ở hàng thứ n từ cột thứ hai đến cột n-1 bằng tổng hai số đứng ở hàng trên cùng cột và cột trước nó. Sở dĩ có quan hệ này là do có công thức truy hồi:

C_n^k=C_n-1^k-1+C_n-1^k (1

Một hình ảnh về tam giác pascal 

Yêu cầu xác định số các số lẻ nằm trên dòng thứ N của tam giác pascal, quy ước đánh số dòng bắt đầu từ 0

Input

Một số dương N (1≤N≤10⁹)

Output

Số các số lẻ nằm trên dòng thứ N

Example

Input:
5

Output:
4