도형으로 타일 채우기

시간 제한1초메모리 제한1024 MB

요약

그림의 모양을 사용해 3×n 타일을 빈칸과 겹침 없이 채우는 방법의 수를 구합니다. n은 60 이하입니다.

문제

정수 $n$ 이 주어진다. 아래 그림에 나온 도형으로 $3 \times n$ 타일을 모두 채우는 방법의 수를 구하라. 채울 때 빈칸이 남으면 안 되고, 도형끼리 겹치면 안 된다.

이 그림은 $n = 4$ 인 경우를 나타낸다. 왼쪽은 도형이고, 오른쪽은 $3 \times n$ 타일이다.

한 줄에 정수 $n$ ( $1 \le n \le 60$ )이 주어진다. $n$ 은 길이이다.

채우는 방법의 수를 출력한다.

첫 번째 예제에서는 채우는 경우가 $4$ 가지 있다.

두 번째 예제에서는 $3 \times 1$ 타일을 이 도형으로 채울 수 없다.