시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB139624955.056%

문제

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

알칸은 수소(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

예제 입력 2

12

예제 출력 2

355
W3sicHJvYmxlbV9pZCI6Ijc3NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjNzc0XHViYzg4IFx1ZDU1OVx1YWUzMFx1YzVkMCBcdWM3MjBcdWFlMzAgXHVkNjU0XHVkNTU5XHVjNzQ0IFx1YzIxOFx1YWMxNVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YzJkY1x1YWMwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhYzA0XHViMmU4XHVkNTVjIFx1YzcyMFx1YWUzMCBcdWJkODRcdWM3OTBcdWM3NzggXHVjNTRjXHVjZTc4XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJjMzBcdWM2ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1Y2U3OFx1Yzc0MCBcdWMyMThcdWMxOGMoSClcdWM2NDAgXHVkMGM0XHVjMThjKEMpIFx1YzZkMFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViZDg0XHVjNzkwXHVjNzc0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MFx1YjI5NCA0XHVhYzFjXHVjNzU4IFx1YWNiMFx1ZDU2OShDLUgsIEMtQyBcdWFjYjBcdWQ1NjkpIFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjMThjIFx1YzZkMFx1Yzc5MFx1YjI5NCBcdWQwYzRcdWMxOGNcdWM2NDAgXHVhY2IwXHVkNTY5XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKEgtQyBcdWFjYjBcdWQ1NjkpPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1Y2U3OCBcdWJkODRcdWM3OTBcdWIyOTQgXHViMmU4XHVjNzdjIFx1YWNiMFx1ZDU2OVx1Yzc3NFx1YmE3MCBcdWMwYWNcdWM3NzRcdWQwNzRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MCBuXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJkODRcdWM3OTBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzIxOFx1YzE4YyBcdWM2ZDBcdWM3OTAgMm4gKyAyXHVhYzFjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YmQ4NFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1Y1x1YjI5NCBDPHN1Yj5uPFwvc3ViPkg8c3ViPjJuKzI8XC9zdWI+XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGM0XHVjMThjIFx1YzZkMFx1Yzc5MFx1YWMwMCBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhZDZjXHVjODcwXHViMjk0IFx1ZDBjNFx1YzE4YyBcdWFjZThcdWFjYTlcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHViMjk0IFx1YmQ4NFx1Yzc5MFx1YzJkZFx1Yzc0MCBcdWFjMTlcdWM5YzBcdWI5Y2MsIFx1ZDBjNFx1YzE4YyBcdWFjZThcdWFjYTlcdWM3NzQgXHViMmU0XHViOTc4IFx1YWM4M1x1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuIFx1ZDBjNFx1YzE4YyBcdWM2ZDBcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzEzOCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YzU0Y1x1Y2U3OFx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWM1NGNcdWNlNzhcdWM3NTggXHVkMGM0XHVjMThjIFx1YWNlOFx1YWNhOVx1Yzc0MCBcdWFjMDBcdWM5YzAgXHVjNWM2XHVjNzc0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHVhZDZjXHVjODcwXHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIEM2SDE0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzQxZGRkMjY5LWI4NmQtNGY2YS1hMDFhLTU3OGM4M2RkOWM4NFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTQ0cHg7IGhlaWdodDogMjQ4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcyMFx1YWUzMCBcdWQ2NTRcdWQ1NTlcdWM3NTggXHVjY2FiIFx1YzIxOVx1YzgxY1x1YjI5NCBcdWQwYzRcdWMxOGMgXHVjNmQwXHVjNzkwXHVhYzAwIG5cdWFjMWNcdWM3NzggXHVjNTRjXHVjZTc4XHVjNzU4IFx1YWQ2Y1x1Yzg3MCBcdWM3NzRcdWMxMzFcdWM5YzhcdWNjYjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0Y1x1Y2U3OFx1Yzc1OCBcdWQwYzRcdWMxOGMgXHVjNmQwXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkNmNcdWM4NzAgXHVjNzc0XHVjMTMxXHVjOWM4XHVjY2I0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNTRjXHVjZTc4XHVjNzU4IFx1ZDBjNFx1YzE4YyBcdWM2ZDBcdWM3OTBcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyA1MCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEM8c3ViPm48XC9zdWI+SDxzdWI+Mm4rMjxcL3N1Yj5cdWM3NTggXHVhZDZjXHVjODcwIFx1Yzc3NFx1YzEzMVx1YzljOFx1Y2NiNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NDAgXHVkNTZkXHVjMGMxIDY0XHViZTQ0XHVkMmI4IFx1YzgxNVx1YzIxOCBcdWQwYzBcdWM3ODUgXHViYzk0XHVjNzA0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijc3NzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDaGVtaXN0cnkiLCJkZXNjcmlwdGlvbiI6IjxwPllvdW5nIENvbGluIGhhcyByZWNlbnRseSBzdGFydGVkIGhpcyBvcmdhbmljIGNoZW1pc3RyeSBsZXNzb25zLiBIaXMgY291cnNlIGhhcyBiZWd1biB3aXRoIHRoZSBzaW1wbGVzdCBvcmdhbmljIG1vbGVjdWxlcyBjYWxsZWQgYWxrYW5lcy48XC9wPlxyXG5cclxuPHA+QWxrYW5lcyBhcmUgbW9sZWN1bGVzIHRoYXQgY29uc2lzdCBvbmx5IG9mIGh5ZHJvZ2VuIChIKSBhbmQgY2FyYm9uIChDKSBhdG9tcy4gRWFjaCBjYXJib24gYXRvbSBoYXMgZXhhY3RseSA0IGJvbmRzIChlaXRoZXIgQyZtaW51cztIIG9yIEMmbWludXM7QyBib25kcyksIGFuZCBlYWNoIGh5ZHJvZ2VuIGF0b20gaXMgam9pbmVkIHRvIGEgY2FyYm9uIGF0b20gKEgmbWludXM7QyBib25kKS4gQW4gYWxrYW5lIG1vbGVjdWxlIGhhcyBvbmx5IHNpbmdsZSBib25kcyBhbmQgaGFzIG5vIGN5Y2xlcy4gQSBtb2xlY3VsZSB3aXRoIG4gYXRvbXMgb2YgY2FyYm9uIGFsd2F5cyBoYXMgMm4gKyAyIGF0b21zIG9mIGh5ZHJvZ2VuIGFuZCBpcyB1c3VhbGx5IHdyaXR0ZW4gYXMgQzxzdWI+bjxcL3N1Yj5IPHN1Yj4ybisyPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+QSBzZXJpZXMgb2YgbGlua2VkIGNhcmJvbiBhdG9tcyBpcyBrbm93biBhcyB0aGUgY2FyYm9uIHNrZWxldG9uLiBEaVx1ZmIwMGVyZW50IGNhcmJvbiBza2VsZXRvbnMgY29ycmVzcG9uZCB0byBkaVx1ZmIwMGVyZW50IGFsa2FuZSBzdHJ1Y3R1cmFsIGlzb21lcnMuIFR3byBpc29tZXJzIGFyZSBjb25zaWRlcmVkIHRoZSBzYW1lIGlmIHRoZWlyIGNhcmJvbiBza2VsZXRvbnMgYXJlIGlzb21vcnBoaWMuIEFsa2FuZXMgd2l0aCBtb3JlIHRoYW4gdGhyZWUgY2FyYm9uIGF0b21zIGNhbiBiZSBhcnJhbmdlZCBpbiB2YXJpb3VzIGRpXHVmYjAwZXJlbnQgd2F5cy4gVGhlIHNpbXBsZXN0IGlzb21lciBvZiBhbiBhbGthbmUgaXMgdGhlIG9uZSBpbiB3aGljaCB0aGUgbiBjYXJib24gYXRvbXMgYXJlIGFycmFuZ2VkIGluIGEgc2luZ2xlIGNoYWluIHdpdGggbm8gYnJhbmNoZXMuIEFsbCBcdWZiMDF2ZSBpc29tZXJzIG9mIEM8c3ViPjY8XC9zdWI+SDxzdWI+MTQ8XC9zdWI+IGFyZSBzaG93biBiZWxvdy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC80MWRkZDI2OS1iODZkLTRmNmEtYTAxYS01NzhjODNkZDljODRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU0NHB4OyBoZWlnaHQ6IDI0OHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5BcyBhIHBhcnQgb2YgaGlzIGhvbWV3b3JrIENvbGluIHdhcyBhc2tlZCB0byBjb3VudCB0aGUgbnVtYmVyIG9mIGRpXHVmYjAwZXJlbnQgYWxrYW5lIGlzb21lcnMgd2l0aCBleGFjdGx5IG4gY2FyYm9uIGF0b21zLiBDb2xpbiBpcyBub3QgYWJsZSB0byBjb3VudCB0aGVtIGJ5IGhpbXNlbGYsIHNvIGhlIGFza2VkIHlvdSBmb3IgaGVscC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgbnVtYmVyIG4gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGNhcmJvbiBhdG9tcyBpbiBhbGthbmUgbW9sZWN1bGUgKDEgJmxlOyBuICZsZTsgNTApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2Ygb3V0cHV0IFx1ZmIwMWxlIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgZGlcdWZiMDBlcmVudCBDPHN1Yj5uPFwvc3ViPkg8c3ViPjJuKzI8XC9zdWI+IGlzb21lcnMuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgYW5zd2VyIFx1ZmIwMXRzIHNpZ25lZCA2NC1iaXQgaW50ZWdlciB0eXBlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=