Một dãy nhị phân độ dài ~n~ là một dãy gồm ~n~ chữ số nhị phân (0 hoặc 1).

Yêu cầu:

Cho số nguyên dương ~n~, đếm số dãy nhị phân độ dài ~n~ không chứa hai số 1 liền nhau.
Ví dụ với n=4, ta có 8 dãy như sau: 0000 0001 0010 0100 0101 1000 1001 1010

Dữ liệu:

Một số nguyên dương ~n≤90~.

Kết quả:

Một số nguyên duy nhất là số dãy nhị phân độ dài ~n~ không chứa hai số 1 liền nhau.

Input

4

Output

8