Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm n bậc.

Các bậc thang được đánh số từ 1 đến n từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Biết ban đầu, Lucky đứng ở bậc thang số 1.

Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ n). Bờm muốn nhờ bạn trả lời câu hỏi này.

INPUT

gồm số nguyên n là số bậc của cầu thang (0 ≤ n ≤ 50).

OUTPUT

In ra số cách Lucky leo hết cầu thang.

Ví dụ:

Input

3

Output

2

Ảnh chụp