시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 27 10 7 70.000%

문제

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

알칸은 수소(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+XHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhZDZjXHVjODcwXHViMjk0IFx1ZDBjNFx1YzE4YyBcdWFjZThcdWFjYTlcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHViMjk0IFx1YmQ4NFx1Yzc5MFx1YzJkZFx1Yzc0MCBcdWFjMTlcdWM5YzBcdWI5Y2MsIFx1ZDBjNFx1YzE4YyBcdWFjZThcdWFjYTlcdWM3NzQgXHViMmU0XHViOTc4IFx1YWM4M1x1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1ZDBjNFx1YzE4YyBcdWM2ZDBcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzEzOCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YzU0Y1x1Y2U3OFx1Yzc0MCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVhYzA0XHViMmU4XHVkNTVjIFx1YzU0Y1x1Y2U3OFx1Yzc1OCBcdWQwYzRcdWMxOGMgXHVhY2U4XHVhY2E5XHVjNzQwIFx1YWMwMFx1YzljMCBcdWM1YzZcdWM3NzQgXHVjNzdjXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWFkNmNcdWM4NzBcdWM3NzRcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgQzZIMTRcdWM3NTggXHViYWE4XHViNGUwIFx1YWQ2Y1x1Yzg3MCBcdWM3NzRcdWMxMzFcdWM5YzhcdWNjYjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2hlbWkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjYxcHg7IHdpZHRoOjU4MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcyMFx1YWUzMCBcdWQ2NTRcdWQ1NTlcdWM3NTggXHVjY2FiIFx1YzIxOVx1YzgxY1x1YjI5NCBcdWQwYzRcdWMxOGMgXHVjNmQwXHVjNzkwXHVhYzAwIG5cdWFjMWNcdWM3NzggXHVjNTRjXHVjZTc4XHVjNzU4IFx1YWQ2Y1x1Yzg3MCBcdWM3NzRcdWMxMzFcdWM5YzhcdWNjYjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1Y2U3OFx1Yzc1OCBcdWQwYzRcdWMxOGMgXHVjNmQwXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNTRjXHVjZTc4XHVjNzU4IFx1ZDBjNFx1YzE4YyBcdWM2ZDBcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyA1MCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEM8c3ViPm48XC9zdWI+SDxzdWI+Mm4rMjxcL3N1Yj5cdWM3NTggXHVhZDZjXHVjODcwIFx1Yzc3NFx1YzEzMVx1YzljOFx1Y2NiNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NDAgXHVkNTZkXHVjMGMxIDY0XHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOCBcdWQwYzBcdWM3ODUgXHViYzk0XHVjNzA0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc3NzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDaGVtaXN0cnkiLCJkZXNjcmlwdGlvbiI6IjxwPllvdW5nIENvbGluIGhhcyByZWNlbnRseSBzdGFydGVkIGhpcyBvcmdhbmljIGNoZW1pc3RyeSBsZXNzb25zLiBIaXMgY291cnNlIGhhcyBiZWd1biB3aXRoIHRoZSBzaW1wbGVzdCBvcmdhbmljIG1vbGVjdWxlcyBjYWxsZWQgYWxrYW5lcy48XC9wPlxyXG5cclxuPHA+QWxrYW5lcyBhcmUgbW9sZWN1bGVzIHRoYXQgY29uc2lzdCBvbmx5IG9mIGh5ZHJvZ2VuIChIKSBhbmQgY2FyYm9uIChDKSBhdG9tcy4gRWFjaCBjYXJib24gYXRvbSBoYXMgZXhhY3RseSA0IGJvbmRzIChlaXRoZXIgQyZtaW51cztIIG9yIEMmbWludXM7QyBib25kcyksIGFuZCBlYWNoIGh5ZHJvZ2VuIGF0b20gaXMgam9pbmVkIHRvIGEgY2FyYm9uIGF0b20gKEgmbWludXM7QyBib25kKS4gQW4gYWxrYW5lIG1vbGVjdWxlIGhhcyBvbmx5IHNpbmdsZSBib25kcyBhbmQgaGFzIG5vIGN5Y2xlcy4gQSBtb2xlY3VsZSB3aXRoIG4gYXRvbXMgb2YgY2FyYm9uIGFsd2F5cyBoYXMgMm4gKyAyIGF0b21zIG9mIGh5ZHJvZ2VuIGFuZCBpcyB1c3VhbGx5IHdyaXR0ZW4gYXMgQzxzdWI+bjxcL3N1Yj5IPHN1Yj4ybisyPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+QSBzZXJpZXMgb2YgbGlua2VkIGNhcmJvbiBhdG9tcyBpcyBrbm93biBhcyB0aGUgY2FyYm9uIHNrZWxldG9uLiBEaVx1ZmIwMGVyZW50IGNhcmJvbiBza2VsZXRvbnMgY29ycmVzcG9uZCB0byBkaVx1ZmIwMGVyZW50IGFsa2FuZSBzdHJ1Y3R1cmFsIGlzb21lcnMuIFR3byBpc29tZXJzIGFyZSBjb25zaWRlcmVkIHRoZSBzYW1lIGlmIHRoZWlyIGNhcmJvbiBza2VsZXRvbnMgYXJlIGlzb21vcnBoaWMuIEFsa2FuZXMgd2l0aCBtb3JlIHRoYW4gdGhyZWUgY2FyYm9uIGF0b21zIGNhbiBiZSBhcnJhbmdlZCBpbiB2YXJpb3VzIGRpXHVmYjAwZXJlbnQgd2F5cy4gVGhlIHNpbXBsZXN0IGlzb21lciBvZiBhbiBhbGthbmUgaXMgdGhlIG9uZSBpbiB3aGljaCB0aGUgbiBjYXJib24gYXRvbXMgYXJlIGFycmFuZ2VkIGluIGEgc2luZ2xlIGNoYWluIHdpdGggbm8gYnJhbmNoZXMuIEFsbCBcdWZiMDF2ZSBpc29tZXJzIG9mIEM8c3ViPjY8XC9zdWI+SDxzdWI+MTQ8XC9zdWI+IGFyZSBzaG93biBiZWxvdy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGVtaS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNjFweDsgd2lkdGg6NTgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QXMgYSBwYXJ0IG9mIGhpcyBob21ld29yayBDb2xpbiB3YXMgYXNrZWQgdG8gY291bnQgdGhlIG51bWJlciBvZiBkaVx1ZmIwMGVyZW50IGFsa2FuZSBpc29tZXJzIHdpdGggZXhhY3RseSBuIGNhcmJvbiBhdG9tcy4gQ29saW4gaXMgbm90IGFibGUgdG8gY291bnQgdGhlbSBieSBoaW1zZWxmLCBzbyBoZSBhc2tlZCB5b3UgZm9yIGhlbHAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIHRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIG51bWJlciBuICZtZGFzaDsgdGhlIG51bWJlciBvZiBjYXJib24gYXRvbXMgaW4gYWxrYW5lIG1vbGVjdWxlICgxICZsZTsgbiAmbGU7IDUwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIG91dHB1dCBcdWZiMDFsZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIGRpXHVmYjAwZXJlbnQgQzxzdWI+bjxcL3N1Yj5IPHN1Yj4ybisyPFwvc3ViPiBpc29tZXJzLiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgdGhlIGFuc3dlciBcdWZiMDF0cyBzaWduZWQgNjQtYml0IGludGVnZXIgdHlwZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=