시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB39171448.276%

문제

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

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

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

입력

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

출력

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

예제 입력 1

3 2

예제 출력 1

8

예제 입력 2

1 1

예제 출력 2

1

예제 입력 3

2 1

예제 출력 3

1

예제 입력 4

2 2

예제 출력 4

2

예제 입력 5

3 1

예제 출력 5

1
W3sicHJvYmxlbV9pZCI6IjIzMjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWM1NjBcdWJiM2MgXHVjMTI0XHVhY2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzZDlcdWFkZGMgXHVjY2I0XHVjNzIxXHVhZDAwXHVjNWQwXHVjMTFjIFx1YzdhNVx1YzU2MFx1YmIzYyBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhY2JkXHVhZTMwXHVjN2E1XHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IG1cdWFjMWNcdWM3NTggXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0IFx1Yzc3Y1x1YjgyY1x1Yjg1YyBcdWMxMWMgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjN2E1XHVjNTYwXHViYjNjXHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYzFiXHVjZTY4XHViMzAwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1YzEyNFx1YWNjNFx1ZDU2MCBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjIFx1YzYwNlx1YzVkMCBcdWIyZTRcdWI5NzggXHVjN2E1XHVjNTYwXHViYjNjXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWI0NTAgXHViYzFiXHVjZTY4XHViMzAwIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWFjMDBcdWI5NzggXHViMmU0XHVjNzRjLCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI0ZTRcdWM3NDQgXHViMDdjXHVjNmNjIFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMgXHViMDdjXHVjNmNjIFx1YjEyM1x1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI0ZTRcdWM3NDAgXHViYzE4XHViNGRjXHVjMmRjIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWFjMDBcdWI5NzggXHVjNmQwXHViNzk4IFx1YzdhNVx1YzU2MFx1YmIzY1x1YmNmNFx1YjJlNCBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMTkyXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAxMVwvZGQuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6NzVweDsgd2lkdGg6Mzc4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViOWJjXHVjNzU4IFx1YzY3Y1x1Y2FiZFx1Yzc0MCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQwIFx1Yzc3NFx1YjdmMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YjljY1x1YjRlMCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTVjIFx1YjRhNCwgXHVjNjdjXHVjYWJkIFx1YjU0NVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjU0NVx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YWNiZFx1YWUzMFx1Yjk3YyBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWFjYmRcdWFlMzBcdWI5N2MgXHVkNTU4XHViMjk0IFx1YjNjNFx1YzkxMSBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMGFlXHVjNzQwIFx1YzdhNVx1YzU2MFx1YmIzYyhcdWQ2MzlcdWM3NDAgXHViNTQ1KVx1YzVkMFx1YzExYyBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMTkyXHVjNzQwIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0IFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc1OCBcdWIwOWNcdWM3NzRcdWIzYzRcdWFjMDAgMVx1YzUyOSBcdWM5OWRcdWFjMDBcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWI5ZTggXHVjYzk4XHVjNzRjIFx1YjU0NVx1YzVkMFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1YzVkMFx1YzExYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1YzVkMFx1YzExYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViOWM4XHVjOWMwXHViOWM5IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YzVlYywgXHViMDljXHVjNzc0XHViM2M0XHVhYzAwIDRcdWFjMDAgXHViNDFjXHViMmU0LiBcdWFkZjggXHVjNjc4XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIxOTJcdWM3NzRcdWFjMDAgXHViMTkyXHVjNzQwIFx1YWNmM1x1YzVkMFx1YzExYyBcdWIwYWVcdWM3NDAgXHVhY2YzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NzRcdWJiYzBcdWI4NWMgXHViMDljXHVjNzc0XHViM2M0XHVjNWQwIFx1YWNjNFx1YzBiMFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjN2E1XHVjNTYwXHViYjNjIFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc1OCBcdWIwOWNcdWM3NzRcdWIzYzQga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBtXHVhYzFjXHVjNzU4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBtKDAgJmxlOyBtICZsZTsgNTApLCBrKDAgJmxlOyBrICZsZTsgMTI4KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0MCAxMFx1YzljNFx1YzIxOCAxMDBcdWM3OTBcdWI5YWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzI5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2xhZGlhdG9ycyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIFRWIGdhbWUgc2hvdyBHbGFkaWF0b3JzLCB0aGUgZmluYWwgY29tcGV0aXRpb24gaXMgdG8gcnVuIHRocm91Z2ggYSBzdGVlcGxlY2hhc2UgY291cnNlLiBUbyBnZXQgc29tZSB2YXJpYXRpb24sIHRoZSBwcm9kdWNlciBoYXMgZGVjaWRlZCB0byBjaGFuZ2UgdGhlIGNvdXJzZSBlYWNoIHdlZWsuIFRoZSBjb3Vyc2UgaXMgYWx3YXlzIGJ1aWx0IG91dCBvZiBtIG9ic3RhY2xlcywgYWxsIG9mIGRpZmZlcmVudCBoZWlnaHRzLCBwbGFjZWQgYWxvbmcgYSBzdHJhaWdodCBsaW5lLiBBbiBvYnN0YWNsZSBjb25zaXN0cyBvZiB0d28gaW5pdGlhbGx5IGNvbm5lY3RlZCBwbGF0Zm9ybXMgd2hpY2ggbWF5IGJlIHNlcGFyYXRlZC4gQmV0d2VlbiB0aGUgdHdvIHBsYXRmb3JtcyBvZiBhbiBvYnN0YWNsZSwgb3RoZXIgaGlnaGVyIG9ic3RhY2xlcyBtYXkgYmUgcHV0LiBBbHNvLCBvYnN0YWNsZXMgbWF5IGJlIHB1dCBhZnRlciBvbmUgYW5vdGhlci48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9nbGFkaS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMTRweDsgd2lkdGg6NjA4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEuIFRvIHRoZSBsZWZ0OiBBbiBvYnN0YWNsZSBzZWVuIGZyb20gdGhlIHNpZGUuIFRvIHRoZSByaWdodDogQSBzdGVlcGxlY2hhc2UgY291cnNlIGNvbnNpc3Rpbmcgb2YgNSBvYnN0YWNsZXMuIFRoZSBjb250ZXN0YW50cyBydW4gZnJvbSBsZWZ0IHRvIHJpZ2h0LjxcL3A+XHJcblxyXG48cD5UaGUgcHJvZHVjZXIgdGhpbmtzIGl0IGlzIG1vc3QgZGVzaXJhYmxlIHRoYXQgdGhlIHJlc3VsdHMgZnJvbSBkaWZmZXJlbnQgd2Vla3MgbWF5IGJlIGNvbXBhcmVkIHRvIGVhY2ggb3RoZXIuIFRoZXJlZm9yZSwgaGUgd2FudHMgdG8gYnVpbGQgY291cnNlcyBvZiBzaW1pbGFyIGRlZ3JlZSBvZiBkaWZmaWN1bHR5LiBBIHByb3Bvc2VkIG1lYXN1cmUgb2YgZGlmZmljdWx0eSBpcyB0aGUgbnVtYmVyIG9mIHBsYXRmb3JtcyB0aGF0IGFyZSBoaWdoZXIgdGhhbiB0aGVpciBpbW1lZGlhdGVseSBwcmVjZWVkaW5nIHBsYXRmb3JtIGFsb25nIHRoZSBjb3Vyc2UuIE1vcmVvdmVyLCB0aGUgbGVmdG1vc3QgKGZpcnN0KSBwbGF0Zm9ybSBvZiB0aGUgY291cnNlIGFsd2F5cyBnaXZlIHJpc2UgdG8gb25lIHBvaW50IHNpbmNlIGl0IGlzIGxvY2F0ZWQgYWJvdmUgdGhlIGZsb29yLiBFLmcuIHRoZSBjb3Vyc2UgdG8gdGhlIHJpZ2h0IGluIGZpZ3VyZSAxIGhhcyBmb3VyIHBvaW50cyBvZiBkaWZmaWN1bHR5LjxcL3A+XHJcblxyXG48cD5Zb3VyIG1pc3Npb24gaXMgdG8gZmluZCBvdXQgaG93IG1hbnkgd2F5cyB0aGVyZSBhcmUgdG8gYnVpbGQgYSBjb3Vyc2Ugb2YgYSBnaXZlbiBwb2ludCBvZiBkaWZmaWN1bHR5LCBmcm9tIGEgZ2l2ZW4gbnVtYmVyIG9mIG9ic3RhY2xlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGlzIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgbiwgdGVsbGluZyB0aGUgbnVtYmVyIG9mIHRlc3Qgc2NlbmFyaW9zIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IHNjZW5hcmlvIGNvbnNpc3RzIG9mIG9uZSBsaW5lIGNvbnRhaW5pbmcgdHdvIG5vbiBuZWdhdGl2ZSBpbnRlZ2VycyBtIGFuZCBrLCB3aGVyZSBtICZsZTsgNTAgaXMgdGhlIG51bWJlciBvZiBvYnN0YWNsZXMsIGFuZCBrIGlzIHRoZSBwb2ludCBvZiBkaWZmaWN1bHR5IGFza2VkIGZvci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IHNjZW5hcmlvLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIGVxdWFsIHRvIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGNvdXJzZXMgY29uc3RydWN0YWJsZSBmcm9tIHRoZSBtIG9ic3RhY2xlcywgYW1vdW50aW5nIHRvIGEgcG9pbnQgb2YgZGlmZmljdWx0eSBvZiBleGFjdGx5IGsuIFlvdSBtYXkgc2FmZWx5IGFzc3VtZSB0aGF0IHRoZSBhbnN3ZXIgaXMgbGVzcyB0aGFuIDEwPHN1cD4xMDA8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=