문제
태현이가 2xn 크기의 판을 1x2, 2x2 크기의 타일로 빈틈없이 채우고자 한다. 타일 채우기를 하던 태현이는 타일을 채우는 방법이 단순히 한가지 만 있는 것이 아니고 여러 가지가 있다는 것을 알게 되었다. 태현이가 모든 가지수를 새보고 싶었지만 타일이 크기 때문에 (n≤30) 태현이의 절친한 친구인 당신이 제작한 프로그램으로 모든 가지수를 알아보고자 한다.
단 여기서 태현이가 전제조건을 달았는데 이는 다음과 같다.
위의 두 개의 그림의 경우 왼쪽에서 오른쪽으로 볼 경우에는 다른 모양이지만, 좌우를 뒤집으면 서로 같은 그림으로 보이기 때문에 이러한 그림은 하나로 친다.
입력
첫 번째 줄에는 타일의 길이 N(1≤N≤30)이 주어진다.
출력
입력에 대한 가지수를 출력한다.
예제
4
8
로그인해야 코드를 작성할 수 있어요.