Các nhà bác học tìm thấy một loại vi khuẩn mới khi lớp băng vĩnh cửu bị tan. Họ quyết định nhân giống để nghiên cứu. Đĩa chứa dung môi có hình chữ nhật và có thể coi là một lưới ô vuông kích thước vô hạn.

Ở thời điểm 1, vi khuẩn được cấy vào một ô. Cứ sau một đơn vị thời gian, vi khuẩn lại phát triển sang các ô bên cạnh:

• Ở thời điểm chẵn, vi khuẩn lan từ ô đã có sang ô kề cạnh chưa có vi khuẩn.
• Ở thời điểm lẻ, vi khuẩn lan sang ô kề cạnh và kề đỉnh chưa có vi khuẩn.

Hãy xác định số ô có vi khuẩn sau k đơn vị thời gian.

Input

• Gồm một dòng duy nhất chứa số tự nhiên k (1 ≤ k ≤ 10⁹).

Output

• Đưa ra một số tự nhiên duy nhất là số ô có vi khuẩn sau k đơn vị thời gian.