돌 게임

시간 제한1초메모리 제한1024 MB

요약

세 더미의 돌 개수가 각각 범위에서 무작위로 정해질 때, 앨리스가 이기는 확률을 10^9+7로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 9점
유형: 조합론, 비트 연산, 게임 이론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

앨리스와 밥이 돌이 든 3개의 더미로 게임을 한다. 두 사람은 번갈아 차례를 진행한다. 각 차례에 플레이어는 돌이 남아 있는 더미 하나를 고르고, 그 더미에서 양의 개수만큼 돌을 제거한다. 마지막으로 남은 더미의 마지막 돌을 제거한 사람이 이긴다. 앨리스가 먼저 시작한다.

문제

$i$ 번째 더미의 돌 개수는 $[L_i, R_i]$ 범위에서 균등하게 무작위로 정해진다. 두 사람이 최적으로 플레이할 때, 앨리스가 이길 확률을 구하라.

입력

입력은 정수 6개 $L_1$ , $R_1$ , $L_2$ , $R_2$ , $L_3$ , $R_3$ 가 한 줄에 주어진다. 각 $i$ 에 대해 $1 \le L_i \le R_i \le 10^9$ 이다.

출력

앨리스가 이길 확률을 $10^9 + 7$ 로 나눈 나머지를 출력한다. 답은 기약분수 $\frac{p}{q}$ 로 나타낼 수 있으며, $q \not\equiv 0 \pmod{10^9 + 7}$ 이다. $p \times q^{-1}$ 을 $10^9 + 7$ 로 나눈 나머지를 출력한다.

예제4

예제 1
입력
```
3 3 4 4 5 5
```
예상 출력
```
1
```
예제 2
입력
```
4 4 8 8 12 12
```
예상 출력
```
0
```
예제 3
입력
```
1 10 1 10 1 10
```
예상 출력
```
580000005
```
예제 4
입력
```
5 15 2 9 35 42
```
예상 출력
```
1
```