문제 설명

신입 인테리어 기사 도라는 폭이 2칸인 긴 복도에 타일을 깔아야 합니다. 창고에는 1×2 크기(가로로 눕힌 모양)와 2×1 크기(세로로 세운 모양)의 똑같은 타일만 잔뜩 쌓여 있습니다. 복도의 길이가 n칸일 때, 빈틈도 겹침도 없이 복도를 가득 채우는 서로 다른 타일 배치는 모두 몇 가지일까요?

입력

출력

제약 조건

• •1 <= n <= 45
• •타일은 회전만 가능하며, 1×2와 2×1 두 종류만 사용한다

예제

3

3

6

13