Dãy nhị phân

Nam là một học sinh thông minh, cần cù chịu khó. Vì muốn các bạn trong cùng đội tuyển cùng nhớ lại kiến thức về dãy nhị phân, Nam đã đưa ra một đề bài như sau: Cho trước số nguyên dương $n$ ($n\le 50$). Hãy đếm số lượng xâu nhị phân có độ dài $n$ mà trong xâu đó không có $2$ kí tự 1 nào đứng cạnh nhau. Các em hãy cùng giải đề mà Nam đưa ra nhé!

Yêu cầu: Tính số lượng xâu nhị phân có độ dài $n$ (mỗi kí tự là 0 hoặc 1) thỏa mãn điều kiện không có $2$ kí tự 1 nào đứng cạnh nhau.

Dữ liệu vào

Một số nguyên dương duy nhất $n$.

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng xâu nhị phân có độ dài $n$ mà trong xâu đó không có $2$ kí tự 1 nào đứng cạnh nhau.

Ràng buộc

• $1\le n\le 50$.

Subtasks

• Subtask 1 ($60\%$ số điểm): $n\le 20$.
• Subtask 2 ($40\%$ số điểm): $20<n\le 50$.

Ví dụ