시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 72 34 23 50.000%

문제

준규는 화학과 대학원생이다. 준규의 랩에서는 최근 흥미로운 테입을 발견했다. 이 테입은 N개의 서로 같은 길이의 조각으로 이뤄져 있는데, 두 조각 사이는 쉽게 구부러지지만 정확히 180도로만 구부러진다.

테입의 한 면은 매우 불안정한 휘발성 화학물질로 코팅되어 있다. 만약 이 코팅된 면끼리 닿는다면 엄청난 폭발이 일어날 것이다.

테입의 다른 한 면은 아직 다 코팅이 끝나지 않아서, 테입의 처음 A개 조각과 끝의 B개 조각만 코팅이 되어 있다. 물론 이 면의 코팅도 같은 화학물질로 코팅되어 있기 때문에 서로 닿으면 폭발한다.

준규는 이 테입이 폭발하지 않도록 구부릴 수 있는 방법의 수를 알고싶어 한다. 이 테입은 한 번 이상 구부릴 수 있으며, 두 조각 사이를 구부린 방법이 하나라도 다르면 다른 방법으로 센다.

답이 매우 커질 수 있기 때문에 방법의 수를 10301로 나눈 나머지를 출력한다.

아래 예시는 N=4, A=1, B=1일 때 가능한 방법의 수를 나타낸 것이다. 단, 아래 그림에서는 편의를 위해 90도 구부린 것으로 그려져 있지만 실제 준규는 이 테입을 180도로 구부린다.

입력

입력의 첫 줄에 자연수 N, A, B(A>0, B>0, A+B ≤ N ≤ 1000)가 주어진다. N은 조각의 수, A는 테입의 왼쪽에 코팅된 조각의 수, B는 테잎의 오른쪽에 코팅된 조각의 수이다.

출력

가능한 방법의 수를 10301로 나눈 나머지를 출력한다.

예제 입력 1

4 1 1

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjI5MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWRcdWJjMWMgXHVjMGFjXHVhY2UwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVkNjU0XHVkNTU5XHVhY2ZjIFx1YjMwMFx1ZDU1OVx1YzZkMFx1YzBkZFx1Yzc3NFx1YjJlNC4gXHVjOTAwXHVhZGRjXHVjNzU4IFx1YjdhOVx1YzVkMFx1YzExY1x1YjI5NCBcdWNkNWNcdWFkZmMgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1ZDE0Y1x1Yzc4NVx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWQxNGNcdWM3ODVcdWM3NDAgTlx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOTA0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViNDUwIFx1Yzg3MFx1YWMwMSBcdWMwYWNcdWM3NzRcdWIyOTQgXHVjMjdkXHVhYzhjIFx1YWQ2Y1x1YmQ4MFx1YjdlY1x1YzljMFx1YzljMFx1YjljYyBcdWM4MTVcdWQ2NTVcdWQ3ODggMTgwXHViM2M0XHViODVjXHViOWNjIFx1YWQ2Y1x1YmQ4MFx1YjdlY1x1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjNzg1XHVjNzU4IFx1ZDU1YyBcdWJhNzRcdWM3NDAgXHViOWU0XHVjNmIwIFx1YmQ4OFx1YzU0OFx1YzgxNVx1ZDU1YyBcdWQ3MThcdWJjMWNcdWMxMzEgXHVkNjU0XHVkNTU5XHViYjNjXHVjOWM4XHViODVjIFx1Y2Y1NFx1ZDMwNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM3NzQgXHVjZjU0XHVkMzA1XHViNDFjIFx1YmE3NFx1YjA3Y1x1YjlhYyBcdWIyZmZcdWIyOTRcdWIyZTRcdWJhNzQgXHVjNWM0XHVjY2FkXHViMDljIFx1ZDNlZFx1YmMxY1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwYTAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWM3ODVcdWM3NTggXHViMmU0XHViOTc4IFx1ZDU1YyBcdWJhNzRcdWM3NDAgXHVjNTQ0XHVjOWMxIFx1YjJlNCBcdWNmNTRcdWQzMDVcdWM3NzQgXHViMDVkXHViMDk4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzExYywgXHVkMTRjXHVjNzg1XHVjNzU4IFx1Y2M5OFx1Yzc0YyBBXHVhYzFjIFx1Yzg3MFx1YWMwMVx1YWNmYyBcdWIwNWRcdWM3NTggQlx1YWMxYyBcdWM4NzBcdWFjMDFcdWI5Y2MgXHVjZjU0XHVkMzA1XHVjNzc0IFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWM3NzQgXHViYTc0XHVjNzU4IFx1Y2Y1NFx1ZDMwNVx1YjNjNCBcdWFjMTlcdWM3NDAgXHVkNjU0XHVkNTU5XHViYjNjXHVjOWM4XHViODVjIFx1Y2Y1NFx1ZDMwNVx1YjQxOFx1YzViNCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzExY1x1Yjg1YyBcdWIyZmZcdWM3M2NcdWJhNzQgXHVkM2VkXHViYzFjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVjNzc0IFx1ZDE0Y1x1Yzc4NVx1Yzc3NCBcdWQzZWRcdWJjMWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1YWQ2Y1x1YmQ4MFx1YjliNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjNTRjXHVhY2UwXHVjMmY2XHVjNWI0IFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1ZDE0Y1x1Yzc4NVx1Yzc0MCBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWFkNmNcdWJkODBcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViNDUwIFx1Yzg3MFx1YWMwMSBcdWMwYWNcdWM3NzRcdWI5N2MgXHVhZDZjXHViZDgwXHViOWIwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWQ1NThcdWIwOThcdWI3N2NcdWIzYzQgXHViMmU0XHViOTc0XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjMTNjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjVcdWM3NzQgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEwMzAxXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVjNjA4XHVjMmRjXHViMjk0IE49NCwgQT0xLCBCPTFcdWM3N2MgXHViNTRjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJlOCwgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExY1x1YjI5NCBcdWQzYjhcdWM3NThcdWI5N2MgXHVjNzA0XHVkNTc0IDkwXHViM2M0IFx1YWQ2Y1x1YmQ4MFx1YjliMCBcdWFjODNcdWM3M2NcdWI4NWMgXHVhZGY4XHViODI0XHVjODM4IFx1Yzc4OFx1YzljMFx1YjljYyBcdWMyZTRcdWM4MWMgXHVjOTAwXHVhZGRjXHViMjk0IFx1Yzc3NCBcdWQxNGNcdWM3ODVcdWM3NDQgMTgwXHViM2M0XHViODVjIFx1YWQ2Y1x1YmQ4MFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tb2xhci5wbmdcIiBzdHlsZT1cImZvbnQtc2l6ZTptZWRpdW07IGhlaWdodDozMjFweDsgd2lkdGg6NjQ1cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXGIgXHVjNzkwXHVjNWYwXHVjMjE4IE4sIEEsIEIoQSZndDswLCBCJmd0OzAsIEErQiAmbGU7IE4gJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjODcwXHVhYzAxXHVjNzU4IFx1YzIxOCwgQVx1YjI5NCBcdWQxNGNcdWM3ODVcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwIFx1Y2Y1NFx1ZDMwNVx1YjQxYyBcdWM4NzBcdWFjMDFcdWM3NTggXHVjMjE4LCBCXHViMjk0IFx1ZDE0Y1x1Yzc4ZVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjZjU0XHVkMzA1XHViNDFjIFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMTAzMDFcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS0FCT09NIiwiZGVzY3JpcHRpb24iOiI8cD5MdWthIGZvdW5kIGFuIGludGVyZXN0aW5nIHRhcGUgaW4gdGhlIGNoZW0gbGFiLiBUaGUgdGFwZSBpcyBkaXZpZGVkIGludG8gTiBzZWdtZW50cyBvZiBlcXVhbCBsZW5ndGgsIGFuZCBjYW4gZWFzaWx5IGJlIGJlbnQgYmV0d2VlbiB0d28gc2VnbWVudCwgYnV0IG9ubHkgYnkgZXhhY3RseSAxODAgZGVncmVlcy48XC9wPlxyXG5cclxuPHA+T25lIHNpZGUgb2YgdGhlIHRhcGUgaXMgY29tcGxldGVseSBjb3ZlcmVkIHdpdGggYSB2ZXJ5IHZvbGF0aWxlIGNoZW1pY2FsLiBJZiB0aGUgY2hlbWljYWwgY29tZXMgaW4gY29udGFjdCB3aXRoIGl0c2VsZiwgaXQgcmVhY2hlcyBjcml0aWNhbCBtYXNzIGFuZCBleHBsb2Rlcy48XC9wPlxyXG5cclxuPHA+VGhlIG90aGVyIHNpZGUgb2YgdGhlIHRhcGUgaXMgbm90IGNvbXBsZXRlbHkgY292ZXJlZCB5ZXQuIE9ubHkgdGhlIGZpcnN0IEEgc2VnbWVudHMgYW5kIGxhc3QgQiBzZWdtZW50cyBhcmUgY292ZXJlZCwgd2l0aCB0aGUgZXhhY3Qgc2FtZSBjaGVtaWNhbC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyBMdWthIGNhbiBiZW5kIHRoZSB0YXBlIHNvIHRoYXQgaXQgZG9lcyBub3QgZXhwbG9kZS4gSGUgY2FuIGJlbmQgdGhlIHRhcGUgbW9yZSB0aGFuIG9uY2UgYW5kIHR3byB3YXlzIGFyZSBkaWZmZXJlbnQgaWYgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIGJldmVsIGJldHdlZW4gc2VnbWVudHMgdGhhdCBpcyBub3QgYmVudCBpbiBvbmUgYW5kIGlzIGJlbnQgaW4gdGhlIG90aGVyPFwvcD5cclxuXHJcbjxwPlNpbmNlIHRoZSBzb2x1dGlvbiBjYW4gYmUgaHVnZSwgcHJpbnQgdGhlIHJlc3VsdCBtb2R1bG8gMTAzMDEuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgZXhhbXBsZSBpbGx1c3RyYXRlcyBhbGwgNiBwb3NzaWJsZSB3YXlzIGZvciBOPTQsIEE9MSBhbmQgQj0xLiBGb3IgY2xhcml0eSwgdGhlIHRhcGUgaXMgb25seSBiZW50IDkwIGRlZ3JlZXMgb24gdGhlIGlsbHVzdHJhdGlvbi4gTHVrYSB3b3VsZCBhY3R1YWxseSBiZW5kIGl0IDE4MCBkZWdyZWVzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21vbGFyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMyMXB4OyB3aWR0aDo2NDVweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhyZWUgbmF0dXJhbCBudW1iZXJzIE4sIEEgYW5kIEIgKEEmZ3Q7MCwgQiZndDswLCBBK0IgJmxlOyBOICZsZTsgMTAwMCksIHRvdGFsIG51bWJlciBvZiBzZWdtZW50cywgbnVtYmVyIG9mIGNvdmVyZWQgc2VnbWVudHMgZnJvbSB0aGUgbGVmdCBhbmQgZnJvbSB0aGUgcmlnaHQgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBwb3NzaWJsZSB3YXlzIHRvIGJlbmQgdGhlIHRhcGUgbW9kdWxvIDEwMzAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #4 5번

  • 문제를 번역한 사람: arine
  • 문제의 오타를 찾은 사람: wxogus25