Lát bảng 3 x n

Cho một số nguyên $n$. Bạn cần lát kín một bảng kích thước $3\times n$ bằng các mảnh ghép hình chữ L. Mỗi mảnh có dạng một hình vuông $2\times 2$ bị bỏ đi một ô ở góc, tức là phủ đúng $3$ ô, và có thể xoay theo bất kỳ hướng nào trong $4$ hướng. Sau khi lát:

• Không được để trống ô nào.
• Các mảnh không được chồng lên nhau.

Hãy đếm số cách lát kín bảng $3\times n$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ ($1\le n\le 60$) là chiều dài của bảng.

Dữ liệu ra

In ra một số nguyên là số cách lát kín bảng.

Ràng buộc

• $1\le n\le 60$

Ví dụ