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 và kề đỉnh chưa có vi khuẩn.
• Ở thời điểm lẻ, vi khuẩn lan sang ô kề cạnh chưa có vi khuẩn.

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

Ảnh minh họa

Dữ liệu

Vào từ thiết bị vào chuẩn gồm một dòng chứa số nguyên: 1 ≤ k ≤ ~10^8~

Kết quả

Đưa ra thiết bị ra chuẩn một số nguyên – số ô có vi khuẩn.

Ví dụ

INPUT

5

OUTPUT

69