Cho số nguyên dương ~ n ~ ~ ( 1 ≤ n ≤ 25 ) ~, hãy cho biết có tất cả bao nhiêu xâu có độ dài ~ n ~ chỉ gồm 2 kí tự ‘X’ hoặc ‘Y’ mà không có chứa xâu con ‘XYX’.

Dữ liệu vào

• Số nguyên ~ n ~

Kết quả

• Ghi số lượng xâu thỏa mãn yêu cầu bài toán

Ràng buộc

Ví dụ:

Input 1

3 

Output 1

7