크기가 \(2 \times N\)인 직사각형을 크기가 \(1 \times 2\)인 타일과 \(2 \times 1\)인 타일로 채우려고 한다.

타일을 겹치거나 직사각형의 바깥으로 나가게 놓을 수 없으며, 직사각형의 모든 칸을 빈틈없이 채워야 한다.

아래 그림은 사용할 수 있는 두 타일과 비어 있는 \(2 \times 5\) 직사각형을 나타낸다.

\(2 \times N\) 직사각형을 채우는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직사각형의 가로 길이 \(N\)이 주어진다.

출력

첫째 줄에 \(2 \times N\) 직사각형을 채우는 방법의 수를 출력한다.

제한 사항

• \(1 \le N \le 20\)

예제 입력 1

2

예제 출력 1

2

예제 설명 1

\(2 \times 1\) 타일 두 개를 가로로 나란히 놓는 방법과 \(1 \times 2\) 타일 두 개를 세로로 쌓아 놓는 방법이 있다.

예제 입력 2

5

예제 출력 2

8