Một con ếch đang đứng ở bậc thang số 0.

Mỗi lần, nó có thể nhảy lên 1 hoặc 2 bậc.

Hãy tính số cách khác nhau để con ếch có thể nhảy đến bậc thang số n.

Dữ liệu vào (Input)

Một số nguyên n (0 ≤ n ≤ 50).

Dữ liệu ra (Output)

In ra số cách để con ếch có thể nhảy đến bậc thang số n.

Ví dụ

Input

4

Output

5

Giải thích ví dụ:

Các cách nhảy đến bậc 4 là:

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

→ Có 5 cách.