시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 49 20 14 41.176%

문제

동규 체육관에서 장애물 경기장을 설계하고 있다. 경기장에는 높이가 서로 다른 m개의 장애물이 일렬로 서 있다. 각각의 장애물에는 두 개의 받침대가 있다. 경기장을 설계할 때에는 장애물 옆에 다른 장애물을 놓을 수 있다. 또, 장애물의 두 받침대 사이를 가른 다음, 그 사이에 다른 장애물들을 끼워 넣을 수 있다. 이 때 끼워 넣는 장애물들은 반드시 사이를 가른 원래 장애물보다 높이가 높아야 한다.

그림의 왼쪽은 장애물의 한 예이고, 오른쪽은 이런 장애물들을 이용하여 만든 경기장의 한 예이다. 이와 같이 경기장을 설계한 뒤, 왼쪽 땅에서부터 시작하여 오른쪽 땅에 도달할 때까지 경기를 하게 된다. 경기를 하는 도중 높이가 낮은 장애물(혹은 땅)에서 높이가 높은 장애물로 이동할 때마다 경기장의 난이도가 1씩 증가한다. 오른쪽 경기장의 경우에는, 맨 처음 땅에서 첫 번째 장애물로 이동할 때, 첫 번째 장애물에서 두 번째 장애물로 이동할 때, 두 번째 장애물에서 세 번째 장애물로 이동할 때, 그리고 마지막 장애물로 이동할 때를 계산하여, 난이도가 4가 된다. 그 외의 경우에는 높이가 높은 곳에서 낮은 곳으로 이동하는 경우이므로 난이도에 계산되지 않는다.

우리가 만들 장애물 경기장의 난이도 k가 주어졌을 때, m개의 장애물로 만들 수 있는 경기장의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 m(0≤m≤50), k(0≤k≤128)가 주어진다.

출력

첫째 줄에 경기장의 개수를 출력한다. 이 값은 10진수 100자리를 넘지 않는다.

예제 입력 1

3 2

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjIzMjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWM1NjBcdWJiM2MgXHVjMTI0XHVhY2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWFkZGMgXHVjY2I0XHVjNzIxXHVhZDAwXHVjNWQwXHVjMTFjIFx1YzdhNVx1YzU2MFx1YmIzYyBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhY2JkXHVhZTMwXHVjN2E1XHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IG1cdWFjMWNcdWM3NTggXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWMxMWMgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjN2E1XHVjNTYwXHViYjNjXHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYzFiXHVjZTY4XHViMzAwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1YzEyNFx1YWNjNFx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjIFx1YzYwNlx1YzVkMCBcdWIyZTRcdWI5NzggXHVjN2E1XHVjNTYwXHViYjNjXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWI0NTAgXHViYzFiXHVjZTY4XHViMzAwIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWFjMDBcdWI5NzggXHViMmU0XHVjNzRjLCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI0ZTRcdWM3NDQgXHViMDdjXHVjNmNjIFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjIFx1YjA3Y1x1YzZjYyBcdWIxMjNcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHViNGU0XHVjNzQwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWMwYWNcdWM3NzRcdWI5N2MgXHVhYzAwXHViOTc4IFx1YzZkMFx1Yjc5OCBcdWM3YTVcdWM1NjBcdWJiM2NcdWJjZjRcdWIyZTQgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjE5Mlx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMTFcL2RkLlBOR1wiIHN0eWxlPVwiaGVpZ2h0Ojc1cHg7IHdpZHRoOjM3OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjliY1x1Yzc1OCBcdWM2N2NcdWNhYmRcdWM3NDAgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1ZDU1YyBcdWM2MDhcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCBcdWM3NzRcdWI3ZjAgXHVjN2E1XHVjNTYwXHViYjNjXHViNGU0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWI5Y2NcdWI0ZTAgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzU4IFx1ZDU1YyBcdWM2MDhcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1YzEyNFx1YWNjNFx1ZDU1YyBcdWI0YTQsIFx1YzY3Y1x1Y2FiZCBcdWI1NDVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWI1NDVcdWM1ZDAgXHViM2M0XHViMmVjXHVkNTYwIFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWFjYmRcdWFlMzBcdWI5N2MgXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhY2JkXHVhZTMwXHViOTdjIFx1ZDU1OFx1YjI5NCBcdWIzYzRcdWM5MTEgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjBhZVx1Yzc0MCBcdWM3YTVcdWM1NjBcdWJiM2MoXHVkNjM5XHVjNzQwIFx1YjU0NSlcdWM1ZDBcdWMxMWMgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjE5Mlx1Yzc0MCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIDFcdWM1MjkgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0LiBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHViOWU4IFx1Y2M5OFx1Yzc0YyBcdWI1NDVcdWM1ZDBcdWMxMWMgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YywgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM1ZDBcdWMxMWMgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YywgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM1ZDBcdWMxMWMgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YjljOFx1YzljMFx1YjljOSBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0Y1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWM1ZWMsIFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YWMwMCA0XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVhZGY4IFx1YzY3OFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjE5Mlx1Yzc0MCBcdWFjZjNcdWM1ZDBcdWMxMWMgXHViMGFlXHVjNzQwIFx1YWNmM1x1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzc0XHViYmMwXHViODVjIFx1YjA5Y1x1Yzc3NFx1YjNjNFx1YzVkMCBcdWFjYzRcdWMwYjBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWFjMDAgXHViOWNjXHViNGU0IFx1YzdhNVx1YzU2MFx1YmIzYyBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHViMDljXHVjNzc0XHViM2M0IGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgbVx1YWMxY1x1Yzc1OCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgbSgwJmxlO20mbGU7NTApLCBrKDAmbGU7ayZsZTsxMjgpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQwIDEwXHVjOWM0XHVjMjE4IDEwMFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzMjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHbGFkaWF0b3JzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgVFYgZ2FtZSBzaG93IEdsYWRpYXRvcnMsIHRoZSBmaW5hbCBjb21wZXRpdGlvbiBpcyB0byBydW4gdGhyb3VnaCBhIHN0ZWVwbGVjaGFzZSBjb3Vyc2UuIFRvIGdldCBzb21lIHZhcmlhdGlvbiwgdGhlIHByb2R1Y2VyIGhhcyBkZWNpZGVkIHRvIGNoYW5nZSB0aGUgY291cnNlIGVhY2ggd2Vlay4gVGhlIGNvdXJzZSBpcyBhbHdheXMgYnVpbHQgb3V0IG9mIG0gb2JzdGFjbGVzLCBhbGwgb2YgZGlmZmVyZW50IGhlaWdodHMsIHBsYWNlZCBhbG9uZyBhIHN0cmFpZ2h0IGxpbmUuIEFuIG9ic3RhY2xlIGNvbnNpc3RzIG9mIHR3byBpbml0aWFsbHkgY29ubmVjdGVkIHBsYXRmb3JtcyB3aGljaCBtYXkgYmUgc2VwYXJhdGVkLiBCZXR3ZWVuIHRoZSB0d28gcGxhdGZvcm1zIG9mIGFuIG9ic3RhY2xlLCBvdGhlciBoaWdoZXIgb2JzdGFjbGVzIG1heSBiZSBwdXQuIEFsc28sIG9ic3RhY2xlcyBtYXkgYmUgcHV0IGFmdGVyIG9uZSBhbm90aGVyLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2dsYWRpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExNHB4OyB3aWR0aDo2MDhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gVG8gdGhlIGxlZnQ6IEFuIG9ic3RhY2xlIHNlZW4gZnJvbSB0aGUgc2lkZS4gVG8gdGhlIHJpZ2h0OiBBIHN0ZWVwbGVjaGFzZSBjb3Vyc2UgY29uc2lzdGluZyBvZiA1IG9ic3RhY2xlcy4gVGhlIGNvbnRlc3RhbnRzIHJ1biBmcm9tIGxlZnQgdG8gcmlnaHQuPFwvcD5cclxuXHJcbjxwPlRoZSBwcm9kdWNlciB0aGlua3MgaXQgaXMgbW9zdCBkZXNpcmFibGUgdGhhdCB0aGUgcmVzdWx0cyBmcm9tIGRpZmZlcmVudCB3ZWVrcyBtYXkgYmUgY29tcGFyZWQgdG8gZWFjaCBvdGhlci4gVGhlcmVmb3JlLCBoZSB3YW50cyB0byBidWlsZCBjb3Vyc2VzIG9mIHNpbWlsYXIgZGVncmVlIG9mIGRpZmZpY3VsdHkuIEEgcHJvcG9zZWQgbWVhc3VyZSBvZiBkaWZmaWN1bHR5IGlzIHRoZSBudW1iZXIgb2YgcGxhdGZvcm1zIHRoYXQgYXJlIGhpZ2hlciB0aGFuIHRoZWlyIGltbWVkaWF0ZWx5IHByZWNlZWRpbmcgcGxhdGZvcm0gYWxvbmcgdGhlIGNvdXJzZS4gTW9yZW92ZXIsIHRoZSBsZWZ0bW9zdCAoZmlyc3QpIHBsYXRmb3JtIG9mIHRoZSBjb3Vyc2UgYWx3YXlzIGdpdmUgcmlzZSB0byBvbmUgcG9pbnQgc2luY2UgaXQgaXMgbG9jYXRlZCBhYm92ZSB0aGUgZmxvb3IuIEUuZy4gdGhlIGNvdXJzZSB0byB0aGUgcmlnaHQgaW4gZmlndXJlIDEgaGFzIGZvdXIgcG9pbnRzIG9mIGRpZmZpY3VsdHkuPFwvcD5cclxuXHJcbjxwPllvdXIgbWlzc2lvbiBpcyB0byBmaW5kIG91dCBob3cgbWFueSB3YXlzIHRoZXJlIGFyZSB0byBidWlsZCBhIGNvdXJzZSBvZiBhIGdpdmVuIHBvaW50IG9mIGRpZmZpY3VsdHksIGZyb20gYSBnaXZlbiBudW1iZXIgb2Ygb2JzdGFjbGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBuLCB0ZWxsaW5nIHRoZSBudW1iZXIgb2YgdGVzdCBzY2VuYXJpb3MgdG8gZm9sbG93LiBFYWNoIHRlc3Qgc2NlbmFyaW8gY29uc2lzdHMgb2Ygb25lIGxpbmUgY29udGFpbmluZyB0d28gbm9uIG5lZ2F0aXZlIGludGVnZXJzIG0gYW5kIGssIHdoZXJlIG0gJmxlOyA1MCBpcyB0aGUgbnVtYmVyIG9mIG9ic3RhY2xlcywgYW5kIGsgaXMgdGhlIHBvaW50IG9mIGRpZmZpY3VsdHkgYXNrZWQgZm9yLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3Qgc2NlbmFyaW8sIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgZXF1YWwgdG8gdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgY291cnNlcyBjb25zdHJ1Y3RhYmxlIGZyb20gdGhlIG0gb2JzdGFjbGVzLCBhbW91bnRpbmcgdG8gYSBwb2ludCBvZiBkaWZmaWN1bHR5IG9mIGV4YWN0bHkgay4gWW91IG1heSBzYWZlbHkgYXNzdW1lIHRoYXQgdGhlIGFuc3dlciBpcyBsZXNzIHRoYW4gMTA8c3VwPjEwMDxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d