{"raw_statement":[{"iden":"statement","content":"Billionaires Robin McBobin and Ronald Dump are playing the Game of Chance.\n\nThe game takes $n$ turns. On each turn, one of the players has the right of choice, Robin gets it for the first move. On each turn, an integer chosen uniformly and independently from $1$ to $m$ appears on the screen. The player with the right of choice has to choose whether to take this number and pass the right of choice to the opponent, or to give this number to the opponent but keep the right of choice for themselves.\n\nBoth Robin and Ronald are more interested in dominating their opponent than in gaining scores, so both will choose the option which would maximize the expected difference between their and the opponent's sum of numbers. Both players play optimally.\n\nLet $d_n$ be the expected value of difference between Robin's sum and Ronald's sum after $n$ turns. It may be proven that for $m >= 3$, there exists a rational number $d$ such that $lim limits_{n arrow.r infinity} d_n = d$. You have to find this number.\n\nThe first line of input contains a single integer $t$ which is the number of test cases ($1 <= t <= 5 dot.op 10^5$).\n\nEach test case is given on a single line containing a single integer $m$ ($3 <= m <= 10^9$).\n\nFor each test case, if $d = frac(P, Q)$ such that $P$ and $Q$ are coprime, output $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$.\n\nFor $m = 3$, the answer is $d = 1$. For $m = 4$, the answer is $d = 1. 333... = frac(4, 3)$.\n\n"},{"iden":"input","content":"The first line of input contains a single integer $t$ which is the number of test cases ($1 <= t <= 5 dot.op 10^5$).Each test case is given on a single line containing a single integer $m$ ($3 <= m <= 10^9$)."},{"iden":"output","content":"For each test case, if $d = frac(P, Q)$ such that $P$ and $Q$ are coprime, output $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$."},{"iden":"note","content":"For $m = 3$, the answer is $d = 1$. For $m = 4$, the answer is $d = 1. 333... = frac(4, 3)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"Let $ m \\in \\mathbb{Z} $, $ m \\geq 3 $.  \nLet $ d $ be the limit of the expected difference $ d_n = \\mathbb{E}[\\text{Robin's sum} - \\text{Ronald's sum}] $ as $ n \\to \\infty $, under optimal play.\n\nThe value $ d $ satisfies the functional equation derived from the optimal stopping rule:\n\n$$\nd = \\frac{1}{m} \\sum_{k=1}^{m} \\max\\left(k - d,\\ -k + d\\right)\n$$\n\nThis simplifies to:\n\n$$\nd = \\frac{1}{m} \\sum_{k=1}^{m} |k - d|\n$$\n\nLet $ t = \\lfloor d \\rfloor $, and define $ r = d - t \\in [0,1) $.  \nSplit the sum at the point where $ k \\leq d $ and $ k > d $:\n\n$$\nd = \\frac{1}{m} \\left( \\sum_{k=1}^{\\lfloor d \\rfloor} (d - k) + \\sum_{k=\\lfloor d \\rfloor + 1}^{m} (k - d) \\right)\n$$\n\nLet $ t = \\lfloor d \\rfloor $, then:\n\n$$\nd = \\frac{1}{m} \\left( t d - \\frac{t(t+1)}{2} + \\frac{m(m+1)}{2} - \\frac{t(t+1)}{2} - (m - t)d \\right)\n$$\n\nSimplify:\n\n$$\nd = \\frac{1}{m} \\left( (2t - m)d + \\frac{m(m+1) - 2t(t+1)}{2} \\right)\n$$\n\nMultiply both sides by $ m $:\n\n$$\nm d = (2t - m)d + \\frac{m(m+1) - 2t(t+1)}{2}\n$$\n\nBring terms with $ d $ to left:\n\n$$\nm d - (2t - m)d = \\frac{m(m+1) - 2t(t+1)}{2}\n$$\n\n$$\n(2m - 2t)d = \\frac{m(m+1) - 2t(t+1)}{2}\n$$\n\n$$\nd = \\frac{m(m+1) - 2t(t+1)}{2(2m - 2t)} = \\frac{m(m+1) - 2t(t+1)}{4(m - t)}\n$$\n\nBut $ t = \\lfloor d \\rfloor $, and for $ m \\geq 3 $, it is known that $ d \\in (1, 2) $, so $ t = 1 $.\n\nThus, substitute $ t = 1 $:\n\n$$\nd = \\frac{m(m+1) - 2(1)(2)}{4(m - 1)} = \\frac{m(m+1) - 4}{4(m - 1)}\n$$\n\nSimplify numerator:\n\n$$\nm(m+1) - 4 = m^2 + m - 4\n$$\n\nSo:\n\n$$\nd = \\frac{m^2 + m - 4}{4(m - 1)}\n$$\n\nThis is the closed-form expression for $ d $.\n\n**Final Answer:**\n\n$$\nd = \\frac{m^2 + m - 4}{4(m - 1)}\n$$","simple_statement":"Robin and Ronald play a turn-based game with n rounds. In each round, a random integer from 1 to m appears. The player with the choice can either take the number and give the choice to the opponent, or give the number to the opponent and keep the choice. Both play optimally to maximize their own score minus the opponent’s. Let d be the limit of the expected difference (Robin - Ronald) as n → ∞. Given m, find d as a reduced fraction P/Q, then output P * Q^(-1) mod (10^9 + 7).","has_page_source":false}