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

• Ban đầu chỉ có hai viên sỏi đặt trên một đường thẳng.
• Lượt đặt thứ nhất ~(N = 1)~ thêm một viên sỏi vào trung điếm của hai viên ban đầu.
• Ở lượt đặt thứ hai ~(N = 2)~, đã có ba viên sỏi của lượt trước và đặt thêm hai viên sỏi (được đánh số ~2~) vào vị trí trung điếm của hai đoạn thẳng như trên hình mô tả.

Giả sử luôn có khoảng cách để có thể đặt một viên sỏi vào giữa hai viên sỏi khác.

Hỏi: sau lượt đặt thứ ~N~ có tất 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.

Input Specification

• Dữ liệu nhập vào từ bàn phím gồm một số tự nhiên ~N~ ~(N \le 10^{9})~

Output Specification

• In ra màn hình một số duy nhất là chữ số cuối của số lượng sỏi đã đặt.

Sample Input 1

2

Sample Output 1

5

Sample Input 2

4

Sample Output 2

7