시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 19 12 54.545%

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

6

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6Ijc3NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNzc0XHViYzg4IFx1ZDU1OVx1YWUzMFx1YzVkMCBcdWM3MjBcdWFlMzAgXHVkNjU0XHVkNTU5XHVjNzQ0IFx1YzIxOFx1YWMxNVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YzJkY1x1YWMwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhYzA0XHViMmU4XHVkNTVjIFx1YzcyMFx1YWUzMCBcdWJkODRcdWM3OTBcdWM3NzggXHVjNTRjXHVjZTc4XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJjMzBcdWM2ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1Y2U3OFx1Yzc0MCBcdWMyMThcdWMxOGMoSClcdWM2NDAgXHVkMGM0XHVjMThjKEMpIFx1YzZkMFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViZDg0XHVjNzkwXHVjNzc0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MFx1YjI5NCA0XHVhYzFjXHVjNzU4IFx1YWNiMFx1ZDU2OShDLUgsIEMtQyBcdWFjYjBcdWQ1NjkpIFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjMThjIFx1YzZkMFx1Yzc5MFx1YjI5NCBcdWQwYzRcdWMxOGNcdWM2NDAgXHVhY2IwXHVkNTY5XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKEgtQyBcdWFjYjBcdWQ1NjkpPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1Y2U3OCBcdWJkODRcdWM3OTBcdWIyOTQgXHViMmU4XHVjNzdjIFx1YWNiMFx1ZDU2OVx1Yzc3NFx1YmE3MCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MCBuXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJkODRcdWM3OTBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzIxOFx1YzE4YyBcdWM2ZDBcdWM3OTAgMm4gKyAyXHVhYzFjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YmQ4NFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1Y1x1YjI5NCBDPHN1Yj5uPFwvc3ViPkg8c3ViPjJuKzI8XC9zdWI+XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhZDZjXHVjODcwXHViMjk0IFx1ZDBjNFx1YzE4YyBcdWFjZThcdWFjYTlcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHViMjk0IFx1YmQ4NFx1Yzc5MFx1YzJkZFx1Yzc0MCBcdWFjMTlcdWM5YzBcdWI5Y2MsIFx1ZDBjNFx1YzE4YyBcdWFjZThcdWFjYTlcdWM3NzQgXHViMmU0XHViOTc4IFx1YWM4M1x1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1ZDBjNFx1YzE4YyBcdWM2ZDBcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzEzOCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YzU0Y1x1Y2U3OFx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWM1NGNcdWNlNzhcdWM3NTggXHVkMGM0XHVjMThjIFx1YWNlOFx1YWNhOVx1Yzc0MCBcdWFjMDBcdWM5YzAgXHVjNWM2XHVjNzc0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhZDZjXHVjODcwXHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIEM2SDE0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NoZW1pLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI2MXB4OyB3aWR0aDo1ODBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWFlMzAgXHVkNjU0XHVkNTU5XHVjNzU4IFx1Y2NhYiBcdWMyMTlcdWM4MWNcdWIyOTQgXHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MFx1YWMwMCBuXHVhYzFjXHVjNzc4IFx1YzU0Y1x1Y2U3OFx1Yzc1OCBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWNlNzhcdWM3NTggXHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZDZjXHVjODcwIFx1Yzc3NFx1YzEzMVx1YzljOFx1Y2NiNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU0Y1x1Y2U3OFx1Yzc1OCBcdWQwYzRcdWMxOGMgXHVjNmQwXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgNTApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBDPHN1Yj5uPFwvc3ViPkg8c3ViPjJuKzI8XC9zdWI+XHVjNzU4IFx1YWQ2Y1x1Yzg3MCBcdWM3NzRcdWMxMzFcdWM5YzhcdWNjYjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSA2NFx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMTggXHVkMGMwXHVjNzg1IFx1YmM5NFx1YzcwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3NzcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2hlbWlzdHJ5IiwiZGVzY3JpcHRpb24iOiI8cD5Zb3VuZyBDb2xpbiBoYXMgcmVjZW50bHkgc3RhcnRlZCBoaXMgb3JnYW5pYyBjaGVtaXN0cnkgbGVzc29ucy4gSGlzIGNvdXJzZSBoYXMgYmVndW4gd2l0aCB0aGUgc2ltcGxlc3Qgb3JnYW5pYyBtb2xlY3VsZXMgY2FsbGVkIGFsa2FuZXMuPFwvcD5cclxuXHJcbjxwPkFsa2FuZXMgYXJlIG1vbGVjdWxlcyB0aGF0IGNvbnNpc3Qgb25seSBvZiBoeWRyb2dlbiAoSCkgYW5kIGNhcmJvbiAoQykgYXRvbXMuIEVhY2ggY2FyYm9uIGF0b20gaGFzIGV4YWN0bHkgNCBib25kcyAoZWl0aGVyIEMmbWludXM7SCBvciBDJm1pbnVzO0MgYm9uZHMpLCBhbmQgZWFjaCBoeWRyb2dlbiBhdG9tIGlzIGpvaW5lZCB0byBhIGNhcmJvbiBhdG9tIChIJm1pbnVzO0MgYm9uZCkuIEFuIGFsa2FuZSBtb2xlY3VsZSBoYXMgb25seSBzaW5nbGUgYm9uZHMgYW5kIGhhcyBubyBjeWNsZXMuIEEgbW9sZWN1bGUgd2l0aCBuIGF0b21zIG9mIGNhcmJvbiBhbHdheXMgaGFzIDJuICsgMiBhdG9tcyBvZiBoeWRyb2dlbiBhbmQgaXMgdXN1YWxseSB3cml0dGVuIGFzIEM8c3ViPm48XC9zdWI+SDxzdWI+Mm4rMjxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPkEgc2VyaWVzIG9mIGxpbmtlZCBjYXJib24gYXRvbXMgaXMga25vd24gYXMgdGhlIGNhcmJvbiBza2VsZXRvbi4gRGlcdWZiMDBlcmVudCBjYXJib24gc2tlbGV0b25zIGNvcnJlc3BvbmQgdG8gZGlcdWZiMDBlcmVudCBhbGthbmUgc3RydWN0dXJhbCBpc29tZXJzLiBUd28gaXNvbWVycyBhcmUgY29uc2lkZXJlZCB0aGUgc2FtZSBpZiB0aGVpciBjYXJib24gc2tlbGV0b25zIGFyZSBpc29tb3JwaGljLiBBbGthbmVzIHdpdGggbW9yZSB0aGFuIHRocmVlIGNhcmJvbiBhdG9tcyBjYW4gYmUgYXJyYW5nZWQgaW4gdmFyaW91cyBkaVx1ZmIwMGVyZW50IHdheXMuIFRoZSBzaW1wbGVzdCBpc29tZXIgb2YgYW4gYWxrYW5lIGlzIHRoZSBvbmUgaW4gd2hpY2ggdGhlIG4gY2FyYm9uIGF0b21zIGFyZSBhcnJhbmdlZCBpbiBhIHNpbmdsZSBjaGFpbiB3aXRoIG5vIGJyYW5jaGVzLiBBbGwgXHVmYjAxdmUgaXNvbWVycyBvZiBDPHN1Yj42PFwvc3ViPkg8c3ViPjE0PFwvc3ViPiBhcmUgc2hvd24gYmVsb3cuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlbWkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjYxcHg7IHdpZHRoOjU4MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFzIGEgcGFydCBvZiBoaXMgaG9tZXdvcmsgQ29saW4gd2FzIGFza2VkIHRvIGNvdW50IHRoZSBudW1iZXIgb2YgZGlcdWZiMDBlcmVudCBhbGthbmUgaXNvbWVycyB3aXRoIGV4YWN0bHkgbiBjYXJib24gYXRvbXMuIENvbGluIGlzIG5vdCBhYmxlIHRvIGNvdW50IHRoZW0gYnkgaGltc2VsZiwgc28gaGUgYXNrZWQgeW91IGZvciBoZWxwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiB0aGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBudW1iZXIgbiAmbWRhc2g7IHRoZSBudW1iZXIgb2YgY2FyYm9uIGF0b21zIGluIGFsa2FuZSBtb2xlY3VsZSAoMSAmbGU7IG4gJmxlOyA1MCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiBvdXRwdXQgXHVmYjAxbGUgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBkaVx1ZmIwMGVyZW50IEM8c3ViPm48XC9zdWI+SDxzdWI+Mm4rMjxcL3N1Yj4gaXNvbWVycy4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBhbnN3ZXIgXHVmYjAxdHMgc2lnbmVkIDY0LWJpdCBpbnRlZ2VyIHR5cGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d