Số mật mã

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 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: abbbbbabb; bbbababa; ababba; a; b; bb; …
• Các dãy mật mã viết sai quy tắc: aa; aaa; abbbaabbb; aabbbabbb; 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$.

Đọc từ tệp văn bản SOMM.INP gồm một số nguyên duy nhất $N$ ($1 \le N \le 50$).

Ghi ra tệp văn bản SOMM.OUT gồm một số nguyên duy nhất là số lượng dãy mật mã đúng có độ dài $N$.

• Có 60% số điểm thỏa mãn điều kiện: $1 \le N \le 20$.
• Có 40% số điểm thỏa mãn điều kiện: $20 < N \le 50$.