시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB77372650.980%

문제

준규는 화학과 대학원생이다. 준규의 랩에서는 최근 흥미로운 테입을 발견했다. 이 테입은 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

예제 입력 2

5 2 2

예제 출력 2

1

예제 입력 3

6 1 2

예제 출력 3

7
W3sicHJvYmxlbV9pZCI6IjI5MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzZWRcdWJjMWMgXHVjMGFjXHVhY2UwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVkNjU0XHVkNTU5XHVhY2ZjIFx1YjMwMFx1ZDU1OVx1YzZkMFx1YzBkZFx1Yzc3NFx1YjJlNC4gXHVjOTAwXHVhZGRjXHVjNzU4IFx1YjdhOVx1YzVkMFx1YzExY1x1YjI5NCBcdWNkNWNcdWFkZmMgXHVkNzY1XHViYmY4XHViODVjXHVjNmI0IFx1ZDE0Y1x1Yzc4NVx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWQxNGNcdWM3ODVcdWM3NDAgTlx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWM4NzBcdWFjMDFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOTA0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViNDUwIFx1Yzg3MFx1YWMwMSBcdWMwYWNcdWM3NzRcdWIyOTQgXHVjMjdkXHVhYzhjIFx1YWQ2Y1x1YmQ4MFx1YjdlY1x1YzljMFx1YzljMFx1YjljYyBcdWM4MTVcdWQ2NTVcdWQ3ODggMTgwXHViM2M0XHViODVjXHViOWNjIFx1YWQ2Y1x1YmQ4MFx1YjdlY1x1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjNzg1XHVjNzU4IFx1ZDU1YyBcdWJhNzRcdWM3NDAgXHViOWU0XHVjNmIwIFx1YmQ4OFx1YzU0OFx1YzgxNVx1ZDU1YyBcdWQ3MThcdWJjMWNcdWMxMzEgXHVkNjU0XHVkNTU5XHViYjNjXHVjOWM4XHViODVjIFx1Y2Y1NFx1ZDMwNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM3NzQgXHVjZjU0XHVkMzA1XHViNDFjIFx1YmE3NFx1YjA3Y1x1YjlhYyBcdWIyZmZcdWIyOTRcdWIyZTRcdWJhNzQgXHVjNWM0XHVjY2FkXHViMDljIFx1ZDNlZFx1YmMxY1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwYTAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWM3ODVcdWM3NTggXHViMmU0XHViOTc4IFx1ZDU1YyBcdWJhNzRcdWM3NDAgXHVjNTQ0XHVjOWMxIFx1YjJlNCBcdWNmNTRcdWQzMDVcdWM3NzQgXHViMDVkXHViMDk4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzExYywgXHVkMTRjXHVjNzg1XHVjNzU4IFx1Y2M5OFx1Yzc0YyBBXHVhYzFjIFx1Yzg3MFx1YWMwMVx1YWNmYyBcdWIwNWRcdWM3NTggQlx1YWMxYyBcdWM4NzBcdWFjMDFcdWI5Y2MgXHVjZjU0XHVkMzA1XHVjNzc0IFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWM3NzQgXHViYTc0XHVjNzU4IFx1Y2Y1NFx1ZDMwNVx1YjNjNCBcdWFjMTlcdWM3NDAgXHVkNjU0XHVkNTU5XHViYjNjXHVjOWM4XHViODVjIFx1Y2Y1NFx1ZDMwNVx1YjQxOFx1YzViNCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzExY1x1Yjg1YyBcdWIyZmZcdWM3M2NcdWJhNzQgXHVkM2VkXHViYzFjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDBcdWFkZGNcdWIyOTQgXHVjNzc0IFx1ZDE0Y1x1Yzc4NVx1Yzc3NCBcdWQzZWRcdWJjMWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1YWQ2Y1x1YmQ4MFx1YjliNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjNTRjXHVhY2UwXHVjMmY2XHVjNWI0IFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1ZDE0Y1x1Yzc4NVx1Yzc0MCBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWFkNmNcdWJkODBcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViNDUwIFx1Yzg3MFx1YWMwMSBcdWMwYWNcdWM3NzRcdWI5N2MgXHVhZDZjXHViZDgwXHViOWIwIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWQ1NThcdWIwOThcdWI3N2NcdWIzYzQgXHViMmU0XHViOTc0XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjMTNjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjVcdWM3NzQgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEwMzAxXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVjNjA4XHVjMmRjXHViMjk0IE49NCwgQT0xLCBCPTFcdWM3N2MgXHViNTRjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjJlOCwgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExY1x1YjI5NCBcdWQzYjhcdWM3NThcdWI5N2MgXHVjNzA0XHVkNTc0IDkwXHViM2M0IFx1YWQ2Y1x1YmQ4MFx1YjliMCBcdWFjODNcdWM3M2NcdWI4NWMgXHVhZGY4XHViODI0XHVjODM4IFx1Yzc4OFx1YzljMFx1YjljYyBcdWMyZTRcdWM4MWMgXHVjOTAwXHVhZGRjXHViMjk0IFx1Yzc3NCBcdWQxNGNcdWM3ODVcdWM3NDQgMTgwXHViM2M0XHViODVjIFx1YWQ2Y1x1YmQ4MFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81MmNlNjQ4NC1lODBjLTQyZjUtYTVjZC02ZWM5OTMyYjhiMWNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU5NHB4OyBoZWlnaHQ6IDI4MHB4O1wiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcYiBcdWM3OTBcdWM1ZjBcdWMyMTggTiwgQSwgQihBJmd0OzAsIEImZ3Q7MCwgQStCICZsZTsgTiAmbGU7IDEwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWM4NzBcdWFjMDFcdWM3NTggXHVjMjE4LCBBXHViMjk0IFx1ZDE0Y1x1Yzc4NVx1Yzc1OCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjZjU0XHVkMzA1XHViNDFjIFx1Yzg3MFx1YWMwMVx1Yzc1OCBcdWMyMTgsIEJcdWIyOTQgXHVkMTRjXHVjNzhlXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWNmNTRcdWQzMDVcdWI0MWMgXHVjODcwXHVhYzAxXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxMDMwMVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS0FCT09NIiwiZGVzY3JpcHRpb24iOiI8cD5MdWthIGZvdW5kIGFuIGludGVyZXN0aW5nIHRhcGUgaW4gdGhlIGNoZW0gbGFiLiBUaGUgdGFwZSBpcyBkaXZpZGVkIGludG8gTiBzZWdtZW50cyBvZiBlcXVhbCBsZW5ndGgsIGFuZCBjYW4gZWFzaWx5IGJlIGJlbnQgYmV0d2VlbiB0d28gc2VnbWVudCwgYnV0IG9ubHkgYnkgZXhhY3RseSAxODAgZGVncmVlcy48XC9wPlxyXG5cclxuPHA+T25lIHNpZGUgb2YgdGhlIHRhcGUgaXMgY29tcGxldGVseSBjb3ZlcmVkIHdpdGggYSB2ZXJ5IHZvbGF0aWxlIGNoZW1pY2FsLiBJZiB0aGUgY2hlbWljYWwgY29tZXMgaW4gY29udGFjdCB3aXRoIGl0c2VsZiwgaXQgcmVhY2hlcyBjcml0aWNhbCBtYXNzIGFuZCBleHBsb2Rlcy48XC9wPlxyXG5cclxuPHA+VGhlIG90aGVyIHNpZGUgb2YgdGhlIHRhcGUgaXMgbm90IGNvbXBsZXRlbHkgY292ZXJlZCB5ZXQuIE9ubHkgdGhlIGZpcnN0IEEgc2VnbWVudHMgYW5kIGxhc3QgQiBzZWdtZW50cyBhcmUgY292ZXJlZCwgd2l0aCB0aGUgZXhhY3Qgc2FtZSBjaGVtaWNhbC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyBMdWthIGNhbiBiZW5kIHRoZSB0YXBlIHNvIHRoYXQgaXQgZG9lcyBub3QgZXhwbG9kZS4gSGUgY2FuIGJlbmQgdGhlIHRhcGUgbW9yZSB0aGFuIG9uY2UgYW5kIHR3byB3YXlzIGFyZSBkaWZmZXJlbnQgaWYgdGhlcmUgaXMgYXQgbGVhc3Qgb25lIGJldmVsIGJldHdlZW4gc2VnbWVudHMgdGhhdCBpcyBub3QgYmVudCBpbiBvbmUgYW5kIGlzIGJlbnQgaW4gdGhlIG90aGVyPFwvcD5cclxuXHJcbjxwPlNpbmNlIHRoZSBzb2x1dGlvbiBjYW4gYmUgaHVnZSwgcHJpbnQgdGhlIHJlc3VsdCBtb2R1bG8gMTAzMDEuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgZXhhbXBsZSBpbGx1c3RyYXRlcyBhbGwgNiBwb3NzaWJsZSB3YXlzIGZvciBOPTQsIEE9MSBhbmQgQj0xLiBGb3IgY2xhcml0eSwgdGhlIHRhcGUgaXMgb25seSBiZW50IDkwIGRlZ3JlZXMgb24gdGhlIGlsbHVzdHJhdGlvbi4gTHVrYSB3b3VsZCBhY3R1YWxseSBiZW5kIGl0IDE4MCBkZWdyZWVzLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzUyY2U2NDg0LWU4MGMtNDJmNS1hNWNkLTZlYzk5MzJiOGIxY1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTk0cHg7IGhlaWdodDogMjgwcHg7XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBuYXR1cmFsIG51bWJlcnMgTiwgQSBhbmQgQiAoQSZndDswLCBCJmd0OzAsIEErQiAmbGU7IE4gJmxlOyAxMDAwKSwgdG90YWwgbnVtYmVyIG9mIHNlZ21lbnRzLCBudW1iZXIgb2YgY292ZXJlZCBzZWdtZW50cyBmcm9tIHRoZSBsZWZ0IGFuZCBmcm9tIHRoZSByaWdodCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHdheXMgdG8gYmVuZCB0aGUgdGFwZSBtb2R1bG8gMTAzMDEuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

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