Một hệ thống đèn gồm ~ n ~ bóng đèn được bố trí từ trái qua phải và được đánh số lần lượt từ 1 đến ~ n ~. Mỗi bóng đèn có 2 trạng thái tắt và mở. Người ta ký hiệu trạng thái tắt là ~ 0 ~ và mở là ~ 1 ~. Bóng đèn ở vị trí đầu tiên (vị trí 1) luôn ở trạng thái mở (trạng thái 1).

Yêu cầu: Hãy cho biết có bao nhiêu trạng thái khác nhau của hệ thống đèn gồm ~ n ~ bóng đèn thỏa điều kiện sau:

• Bóng đèn ở vị trí đầu tiên luôn mở.
• Không tồn tại 2 bóng đèn mở bất kỳ liên tiếp nhau trong hệ thống.

Dữ liệu vào

• Số nguyên dương ~ n ~ ~ ( n ≤ 100) ~.

Kết quả

• Ghi một số duy nhất là số trạng thái khác nhau của hệ thống bóng đèn.

Ví dụ:

Input 1

4 

Output 1

3