시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 9 6 66.667%

문제

창영이는 이번 학기에 유기 화학을 수강한다. 첫 시간에는 가장 간단한 유기 분자인 알칸에 대해서 배웠다.

알칸은 수소(H)와 탄소(C) 원자로만 이루어진 분자이다. 각각의 탄소 원자는 4개의 결합(C-H, C-C 결합) 을 가지고 있고, 각각의 수소 원자는 탄소와 결합되어져 있다. (H-C 결합)

알칸 분자는 단일 결합이며 사이클이 존재하지 않는다. 탄소 원자 n개로 이루어진 분자는 항상 수소 원자 2n + 2개를 가지고 있고, 분자식으로는 CnH2n+2로 나타낸다.

탄소 원자가 연결된 구조는 탄소 골격이라고 한다. 구조 이성질체는 분자식은 같지만, 탄소 골격이 다른 것을 말한다. 탄소 원자의 개수가 세 개 이상인 알칸은 여러가지 방법으로 나타낼 수 있다. 가장 간단한 알칸의 탄소 골격은 가지 없이 일직선으로 연결된 구조이다. 아래 그림은 C6H14의 모든 구조 이성질체이다.

유기 화학의 첫 숙제는 탄소 원자가 n개인 알칸의 구조 이성질체의 개수를 구하는 것이다.

알칸의 탄소 원자의 개수가 주어졌을 때, 구조 이성질체의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 알칸의 탄소 원자의 개수 n이 주어진다. (1 ≤ n ≤ 50)

출력

첫째 줄에 CnH2n+2의 구조 이성질체의 개수를 출력한다. 정답은 항상 64비트 정수 타입 범위이다.

예제 입력

6

예제 출력

5

힌트