27371번 - 다전제 승자는? 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 512 MB | 35 | 22 | 20 | 62.500% |
문제
Albert와 Bob은 보드 게임을 즐겨하는데, 주로 다전제를 하여 승자를 가린다.
"$X$선승 다전제"란 최대 $2X-1$번의 게임을 통해 $X$번을 먼저 이긴 사람이 승자가 되는 게임 방식이다. 두 어린이가 하는 보드 게임에 비기는 경우는 없다고 하자. 예를 들어 $X = 3$인 경우 아래와 같은 다양한 결과가 나올 수 있다 (편의상 A는 Albert가 이긴 게임을, B는 Bob이 이긴 게임을 나타낸다):
AAA: 이 경우 Albert가 3승으로 다전제를 승리한다. 4, 5게임은 불필요하므로 진행하지 않는다.BAAA,ABAA,AABA: 이 경우 Albert가 3승으로 다전제를 승리한다. 5게임은 불필요하므로 진행하지 않는다.BBAAA,BAABA,BABAA,ABBAA,ABABA,AABBA: 이 경우 Albert가 3승으로 다전제를 승리한다.- 위의 10가지 결과 이외에도 A와 B를 뒤집으면 Bob이 다전제를 승리하는 10가지 결과를 얻을 수 있다.
두 사람이 다전제를 진행한 후, 당신에게 다음과 같은 아리송한 말을 남겼다: "$M$선승 다전제의 최종 승자는 $M$게임을 먼저 승리한 Bob이지만, 만약 $N$선승 다전제를 했다면 Albert가 이겼을 것이다. 즉 Albert가 먼저 $N$승을 했지만 Bob이 $M$승을 먼저 하여 최종 승자가 되었다. 물론 $N \lt M$ 이다."
이 말을 듣고 당신은 다전제의 결과가 어땠을지, 그리고 몇 가지나 다른 결과가 가능한지 궁금해졌다.
예를 들어 $M = 2$, $N = 1$인 경우, "ABB"로 1게임을 Albert가 이기고 나머지 두 게임을 Bob이 이기는 경우가 유일하다.
다른 예로 $M = 3$, $N = 2$인 경우 아래와 같은 세 가지 결과가 가능하다:
AABBB: 만약 2선승을 하는 다전제라면 Albert가 2게임째에서 다전제를 승리했겠지만, 3선승을 하는 다전제라 Bob이 최종 승자가 된다.ABABB: 만약 2선승을 하는 다전제라면 Albert가 3게임째에서 다전제를 승리했겠지만, 3선승을 하는 다전제라 Bob이 최종 승자가 된다.BAABB: 만약 2선승을 하는 다전제라면 Albert가 3게임째에서 다전제를 승리했겠지만, 3선승을 하는 다전제라 Bob이 최종 승자가 된다.
입력으로 $N$, $M$ 이 주어졌을 때, Bob이 $M$승을 하여 최종 승자가 되지만 Albert가 먼저 $N$승을 하게되는 다전제의 결과가 몇 가지나 존재하는지 구해보자. 단, 이 수가 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.
입력
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 입력은 한 줄에 $N$, $M$ 두 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- $1 \le T \le 10$
- $1 \le N \lt M \le 10^5$
예제 입력 1
5 1 2 2 3 1 3 2 4 500 1000
예제 출력 1
1 3 4 13 886458341
예제 1: 본문에서 다루었다.
예제 2: 본문에서 다루었다.
예제 3: 다음과 같은 4가지 가능성이 있다: "ABBB", "AABBB" "ABABB", "ABBAB"
예제 4: 추가 설명 없음
예제 5: 답이 매우 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력해야한다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호