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

문제

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

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

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

입력

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

출력

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

예제 입력 1

3 2

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjIzMjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWM1NjBcdWJiM2MgXHVjMTI0XHVhY2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWFkZGMgXHVjY2I0XHVjNzIxXHVhZDAwXHVjNWQwXHVjMTFjIFx1YzdhNVx1YzU2MFx1YmIzYyBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhY2JkXHVhZTMwXHVjN2E1XHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IG1cdWFjMWNcdWM3NTggXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWMxMWMgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjN2E1XHVjNTYwXHViYjNjXHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYzFiXHVjZTY4XHViMzAwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1YzEyNFx1YWNjNFx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjIFx1YzYwNlx1YzVkMCBcdWIyZTRcdWI5NzggXHVjN2E1XHVjNTYwXHViYjNjXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWI0NTAgXHViYzFiXHVjZTY4XHViMzAwIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWFjMDBcdWI5NzggXHViMmU0XHVjNzRjLCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI0ZTRcdWM3NDQgXHViMDdjXHVjNmNjIFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMgXHViMDdjXHVjNmNjIFx1YjEyM1x1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI0ZTRcdWM3NDAgXHViYzE4XHViNGRjXHVjMmRjIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWFjMDBcdWI5NzggXHVjNmQwXHViNzk4IFx1YzdhNVx1YzU2MFx1YmIzY1x1YmNmNFx1YjJlNCBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMTkyXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAxMVwvZGQuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6NzVweDsgd2lkdGg6Mzc4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWJjXHVjNzU4IFx1YzY3Y1x1Y2FiZFx1Yzc0MCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQwIFx1Yzc3NFx1YjdmMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YjljY1x1YjRlMCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTVjIFx1YjRhNCwgXHVjNjdjXHVjYWJkIFx1YjU0NVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjU0NVx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YWNiZFx1YWUzMFx1Yjk3YyBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFjYmRcdWFlMzBcdWI5N2MgXHVkNTU4XHViMjk0IFx1YjNjNFx1YzkxMSBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMGFlXHVjNzQwIFx1YzdhNVx1YzU2MFx1YmIzYyhcdWQ2MzlcdWM3NDAgXHViNTQ1KVx1YzVkMFx1YzExYyBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMTkyXHVjNzQwIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0IFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc1OCBcdWIwOWNcdWM3NzRcdWIzYzRcdWFjMDAgMVx1YzUyOSBcdWM5OWRcdWFjMDBcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWI5ZTggXHVjYzk4XHVjNzRjIFx1YjU0NVx1YzVkMFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1YzVkMFx1YzExYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1YzVkMFx1YzExYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViOWM4XHVjOWMwXHViOWM5IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzVlYywgXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIDRcdWFjMDAgXHViNDFjXHViMmU0LiBcdWFkZjggXHVjNjc4XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMTkyXHVjNzQwIFx1YWNmM1x1YzVkMFx1YzExYyBcdWIwYWVcdWM3NDAgXHVhY2YzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NzRcdWJiYzBcdWI4NWMgXHViMDljXHVjNzc0XHViM2M0XHVjNWQwIFx1YWNjNFx1YzBiMFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjN2E1XHVjNTYwXHViYjNjIFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc1OCBcdWIwOWNcdWM3NzRcdWIzYzQga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBtXHVhYzFjXHVjNzU4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBtKDAmbGU7bSZsZTs1MCksIGsoMCZsZTtrJmxlOzEyOClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDAgMTBcdWM5YzRcdWMyMTggMTAwXHVjNzkwXHViOWFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjMyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdsYWRpYXRvcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBUViBnYW1lIHNob3cgR2xhZGlhdG9ycywgdGhlIGZpbmFsIGNvbXBldGl0aW9uIGlzIHRvIHJ1biB0aHJvdWdoIGEgc3RlZXBsZWNoYXNlIGNvdXJzZS4gVG8gZ2V0IHNvbWUgdmFyaWF0aW9uLCB0aGUgcHJvZHVjZXIgaGFzIGRlY2lkZWQgdG8gY2hhbmdlIHRoZSBjb3Vyc2UgZWFjaCB3ZWVrLiBUaGUgY291cnNlIGlzIGFsd2F5cyBidWlsdCBvdXQgb2YgbSBvYnN0YWNsZXMsIGFsbCBvZiBkaWZmZXJlbnQgaGVpZ2h0cywgcGxhY2VkIGFsb25nIGEgc3RyYWlnaHQgbGluZS4gQW4gb2JzdGFjbGUgY29uc2lzdHMgb2YgdHdvIGluaXRpYWxseSBjb25uZWN0ZWQgcGxhdGZvcm1zIHdoaWNoIG1heSBiZSBzZXBhcmF0ZWQuIEJldHdlZW4gdGhlIHR3byBwbGF0Zm9ybXMgb2YgYW4gb2JzdGFjbGUsIG90aGVyIGhpZ2hlciBvYnN0YWNsZXMgbWF5IGJlIHB1dC4gQWxzbywgb2JzdGFjbGVzIG1heSBiZSBwdXQgYWZ0ZXIgb25lIGFub3RoZXIuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZ2xhZGkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE0cHg7IHdpZHRoOjYwOHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBUbyB0aGUgbGVmdDogQW4gb2JzdGFjbGUgc2VlbiBmcm9tIHRoZSBzaWRlLiBUbyB0aGUgcmlnaHQ6IEEgc3RlZXBsZWNoYXNlIGNvdXJzZSBjb25zaXN0aW5nIG9mIDUgb2JzdGFjbGVzLiBUaGUgY29udGVzdGFudHMgcnVuIGZyb20gbGVmdCB0byByaWdodC48XC9wPlxyXG5cclxuPHA+VGhlIHByb2R1Y2VyIHRoaW5rcyBpdCBpcyBtb3N0IGRlc2lyYWJsZSB0aGF0IHRoZSByZXN1bHRzIGZyb20gZGlmZmVyZW50IHdlZWtzIG1heSBiZSBjb21wYXJlZCB0byBlYWNoIG90aGVyLiBUaGVyZWZvcmUsIGhlIHdhbnRzIHRvIGJ1aWxkIGNvdXJzZXMgb2Ygc2ltaWxhciBkZWdyZWUgb2YgZGlmZmljdWx0eS4gQSBwcm9wb3NlZCBtZWFzdXJlIG9mIGRpZmZpY3VsdHkgaXMgdGhlIG51bWJlciBvZiBwbGF0Zm9ybXMgdGhhdCBhcmUgaGlnaGVyIHRoYW4gdGhlaXIgaW1tZWRpYXRlbHkgcHJlY2VlZGluZyBwbGF0Zm9ybSBhbG9uZyB0aGUgY291cnNlLiBNb3Jlb3ZlciwgdGhlIGxlZnRtb3N0IChmaXJzdCkgcGxhdGZvcm0gb2YgdGhlIGNvdXJzZSBhbHdheXMgZ2l2ZSByaXNlIHRvIG9uZSBwb2ludCBzaW5jZSBpdCBpcyBsb2NhdGVkIGFib3ZlIHRoZSBmbG9vci4gRS5nLiB0aGUgY291cnNlIHRvIHRoZSByaWdodCBpbiBmaWd1cmUgMSBoYXMgZm91ciBwb2ludHMgb2YgZGlmZmljdWx0eS48XC9wPlxyXG5cclxuPHA+WW91ciBtaXNzaW9uIGlzIHRvIGZpbmQgb3V0IGhvdyBtYW55IHdheXMgdGhlcmUgYXJlIHRvIGJ1aWxkIGEgY291cnNlIG9mIGEgZ2l2ZW4gcG9pbnQgb2YgZGlmZmljdWx0eSwgZnJvbSBhIGdpdmVuIG51bWJlciBvZiBvYnN0YWNsZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IHNjZW5hcmlvcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBzY2VuYXJpbyBjb25zaXN0cyBvZiBvbmUgbGluZSBjb250YWluaW5nIHR3byBub24gbmVnYXRpdmUgaW50ZWdlcnMgbSBhbmQgaywgd2hlcmUgbSAmbGU7IDUwIGlzIHRoZSBudW1iZXIgb2Ygb2JzdGFjbGVzLCBhbmQgayBpcyB0aGUgcG9pbnQgb2YgZGlmZmljdWx0eSBhc2tlZCBmb3IuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBzY2VuYXJpbywgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBjb3Vyc2VzIGNvbnN0cnVjdGFibGUgZnJvbSB0aGUgbSBvYnN0YWNsZXMsIGFtb3VudGluZyB0byBhIHBvaW50IG9mIGRpZmZpY3VsdHkgb2YgZXhhY3RseSBrLiBZb3UgbWF5IHNhZmVseSBhc3N1bWUgdGhhdCB0aGUgYW5zd2VyIGlzIGxlc3MgdGhhbiAxMDxzdXA+MTAwPFwvc3VwPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=