시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 109 | 51 | 39 | 48.148% |
준규는 화학과 대학원생이다. 준규의 랩에서는 최근 흥미로운 테입을 발견했다. 이 테입은 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로 나눈 나머지를 출력한다.
4 1 1
6
5 2 2
1
6 1 2
7