Game Of Chance
시간 제한3초메모리 제한512 MB
각 m에 대해, 선택권을 가진 사람이 무작위로 나온 수를 자신이나 상대에게 주는 두 선수 최적 선택 게임에서 점수 차 기댓값의 극한을 구한다.
문제
억만장자 Robin McBobin과 Ronald Dump는 Game of Chance를 하고 있다.
게임은 (n)턴 동안 진행된다. 각 턴마다 두 플레이어 중 한 명이 선택권을 가지며, 첫 턴의 선택권은 Robin이 가진다. 각 턴마다 (1)부터 (m)까지의 정수 하나가 균등하고 독립적으로 화면에 나타난다. 선택권을 가진 플레이어는 이 수를 가져가고 선택권을 상대에게 넘겨줄지, 아니면 이 수를 상대에게 주고 선택권은 자신이 계속 가질지를 정해야 한다.
Robin과 Ronald는 점수를 얻는 것보다 상대를 압도하는 데 더 관심이 있으므로, 둘 다 자신과 상대의 수 합의 차이의 기댓값을 최대화하는 선택을 한다. 두 플레이어는 최적으로 플레이한다.
(d_n)을 (n)턴이 끝난 뒤 Robin의 합과 Ronald의 합의 차이의 기댓값이라고 하자. (m \ge 3)일 때 (\lim_{n \to \infty}{d_n} = d)인 유리수 (d)가 존재함을 증명할 수 있다. 이 수를 구해야 한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 (t)가 주어진다. ((1 \le t \le 5 \cdot 10^5))
각 테스트 케이스는 정수 (m) 하나를 포함하는 한 줄로 주어진다. ((3 \le m \le 10^9))
출력
각 테스트 케이스마다 (d = \frac{P}{Q})이고 (P)와 (Q)가 서로소일 때, ((P \cdot Q^{−1})) mod ((10^9 + 7))을 출력한다. (Q \not\equiv 0) (mod (10^9 + 7))임이 보장된다.
힌트
(m = 3)일 때 답은 (d = 1)이다. (m = 4)일 때 답은 (d = 1.333\dots = \frac{4}{3})이다.