Vào một đợt hội trại, các bạn học sinh tham gia một trò chơi giải mật mã. Các mật mã của trò chơi được tạo ra theo quy tắc như sau: dãy mật mã chỉ gồm hai loại kí tự 'a' hoặc 'b', trong dãy không có từ hai kí tự 'a' trở lên đứng cạnh nhau.

Ví dụ:

• Các dãy mật mã viết đúng quy tắc: abbbbbbab; bbbababa; ababba; a; b; bb; …
• Các dãy mật mã viết sai quy tắc: aa; aaa; abbbaabbb; aabbababb; abbbabbbaa; …

Yêu cầu: Hãy cho biết số lượng các dãy mật mã đúng có độ dài \(N\).

Dữ liệu vào

• Một số nguyên duy nhất \(N\) \((1 \le N \le 50)\).

Dữ liệu ra

• Một số nguyên duy nhất là số lượng dãy mật mã đúng có độ dài \(N\).

Điều kiện

• 60% số điểm thỏa mãn điều kiện: \(1 \le N \le 20\).
• 40% số điểm thỏa mãn điều kiện: \(20 \lt N \le 50\).

Input 1

4

Output 1

8

Input 2

2

Output 2

3