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é!

Dữ liệu vào

• Số nguyên ~n~ duy nhất

Dữ liệu ra

• 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.

Ví dụ

Dữ liệu vào

5

Dữ liệu ra

13

Giải thích:

~13~ xâu nhị phân độ dài ~5~ thỏa mãn điều kiện đề bài là: ~00000,~ ~00001,~ ~00010,~ ~00100,~ ~00101,~ ~01000,~ ~01001,~ ~01010,~ ~10000,~ ~10001,~ ~10010,~ ~10100,~ ~10101~

Giới hạn:

• Subtask ~1~ (~60\%~): ~n \le 20~
• Subtask ~2~ (~40\%~): ~20 < n \le 50~