Yêu cầu

Trên 1 đoạn thẳng, đầu tiên người ta đặt 2 viên sỏi cách xa nhau. Sau đó lặp đi lặp lại các đọng tác sau : Xác định trung điểm giữa 2 viên sỏi liên tiếp trên đoạn thẳng, đặt thêm 1 viên sỏi vào vị trí đó.

• Ban đầu chỉ có 2 viên sỏi đặt trên 1 đường thẳng

• Lượt đặt thứ nhất (N = 1) thêm 1 viên sỏi giữa 2 viên ban đầu

• Lượt đặt thứ hai (N = 2) đã có 3 viên sỏi lượt trước và đặt thêm 2 viên sỏi (được đánh dấu là số 2) vào vị trí trung điểm của 2 đoạn thẳng như trên hình mô tả

• Giả sử luôn có khoảng cách để có thể đặt 1 viên sỏi giữa 2 viên sỏi

• Hỏi sau N lượt đặt thì có bao nhiêu viên sỏi. Vì kết quả có thể rất lớn nên chỉ cần đưa ra chữ số cuối cùng của đáp án

Dữ liệu

• Nhập vào từ bàn phím gồm 1 số tự nhiên \(N\) (\(N ≤ 10^9\)).

Kết quả

• In ra màn hình một số duy nhất là số lượng số thỏa mãn đề bài.

Ví dụ

sample input

2

sample output

5