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~ thỏa mãn điều kiện không có 2 kí tự ‘1’ đứng cạnh nhau.

Input

• Một số nguyên duy nhất ~n~.

Output

• Một số nguyên duy nhất là số lượng xâu nhị phân thỏa mãn yêu cầu.

Sample Input 1

5

Sample Output 1

13