시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 29 19 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+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMTAzMDFcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktBQk9PTSIsImRlc2NyaXB0aW9uIjoiPHA+THVrYSBmb3VuZCBhbiBpbnRlcmVzdGluZyB0YXBlIGluIHRoZSBjaGVtIGxhYi4gVGhlIHRhcGUgaXMgZGl2aWRlZCBpbnRvIE4gc2VnbWVudHMgb2YgZXF1YWwgbGVuZ3RoLCBhbmQgY2FuIGVhc2lseSBiZSBiZW50IGJldHdlZW4gdHdvIHNlZ21lbnQsIGJ1dCBvbmx5IGJ5IGV4YWN0bHkgMTgwIGRlZ3JlZXMuPFwvcD5cclxuXHJcbjxwPk9uZSBzaWRlIG9mIHRoZSB0YXBlIGlzIGNvbXBsZXRlbHkgY292ZXJlZCB3aXRoIGEgdmVyeSB2b2xhdGlsZSBjaGVtaWNhbC4gSWYgdGhlIGNoZW1pY2FsIGNvbWVzIGluIGNvbnRhY3Qgd2l0aCBpdHNlbGYsIGl0IHJlYWNoZXMgY3JpdGljYWwgbWFzcyBhbmQgZXhwbG9kZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBvdGhlciBzaWRlIG9mIHRoZSB0YXBlIGlzIG5vdCBjb21wbGV0ZWx5IGNvdmVyZWQgeWV0LiBPbmx5IHRoZSBmaXJzdCBBIHNlZ21lbnRzIGFuZCBsYXN0IEIgc2VnbWVudHMgYXJlIGNvdmVyZWQsIHdpdGggdGhlIGV4YWN0IHNhbWUgY2hlbWljYWwuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgTHVrYSBjYW4gYmVuZCB0aGUgdGFwZSBzbyB0aGF0IGl0IGRvZXMgbm90IGV4cGxvZGUuIEhlIGNhbiBiZW5kIHRoZSB0YXBlIG1vcmUgdGhhbiBvbmNlIGFuZCB0d28gd2F5cyBhcmUgZGlmZmVyZW50IGlmIHRoZXJlIGlzIGF0IGxlYXN0IG9uZSBiZXZlbCBiZXR3ZWVuIHNlZ21lbnRzIHRoYXQgaXMgbm90IGJlbnQgaW4gb25lIGFuZCBpcyBiZW50IGluIHRoZSBvdGhlcjxcL3A+XHJcblxyXG48cD5TaW5jZSB0aGUgc29sdXRpb24gY2FuIGJlIGh1Z2UsIHByaW50IHRoZSByZXN1bHQgbW9kdWxvIDEwMzAxLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGV4YW1wbGUgaWxsdXN0cmF0ZXMgYWxsIDYgcG9zc2libGUgd2F5cyBmb3IgTj00LCBBPTEgYW5kIEI9MS4gRm9yIGNsYXJpdHksIHRoZSB0YXBlIGlzIG9ubHkgYmVudCA5MCBkZWdyZWVzIG9uIHRoZSBpbGx1c3RyYXRpb24uIEx1a2Egd291bGQgYWN0dWFsbHkgYmVuZCBpdCAxODAgZGVncmVlcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tb2xhci5wbmdcIiBzdHlsZT1cImhlaWdodDozMjFweDsgd2lkdGg6NjQ1cHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIG5hdHVyYWwgbnVtYmVycyBOLCBBIGFuZCBCIChBJmd0OzAsIEImZ3Q7MCwgQStCICZsZTsgTiAmbGU7IDEwMDApLCB0b3RhbCBudW1iZXIgb2Ygc2VnbWVudHMsIG51bWJlciBvZiBjb3ZlcmVkIHNlZ21lbnRzIGZyb20gdGhlIGxlZnQgYW5kIGZyb20gdGhlIHJpZ2h0IHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgcG9zc2libGUgd2F5cyB0byBiZW5kIHRoZSB0YXBlIG1vZHVsbyAxMDMwMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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