시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1470 454 371 30.661%

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 

출력

입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.

예제 입력

2
8
12
100
200

예제 출력

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

힌트