3×N 벽 타일 채우기

세로가 3, 가로가 $N$인 직사각형 벽이 있다. 이 벽을 $2\times1$ 또는 $1\times2$ 크기의 도미노 타일로 빈칸 없이 모두 채우려고 한다.

타일은 서로 겹치면 안 되고, 벽 밖으로 나가도 안 된다. 벽을 채울 수 있는 서로 다른 방법의 수를 구하라.

첫째 줄에 정수 $N$이 주어진다. $(1 \le N \le 30)$

첫째 줄에 $3\times N$ 벽을 타일로 채우는 경우의 수를 출력한다.

아래 그림은 $3\times12$ 벽을 타일로 채운 모습이다.