타일링

2×n 직사각형을 2×1 타일과 2×2 타일만 사용해 빈칸 없이 채우는 방법의 수를 구하시오. 2×1 타일은 가로 또는 세로로 놓을 수 있으며, 타일은 서로 겹치거나 직사각형 밖으로 나갈 수 없다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 하나씩 주어지며, 정수 n이 주어진다.

각 테스트 케이스마다 2×n 직사각형을 채우는 방법의 수를 한 줄에 하나씩 출력한다.

• 0 ≤ n ≤ 250