{"problem":{"name":"K. Expected Value","description":{"content":"Here is a game played with sequence $a_1, \\\\dots, a_n$. On each turn, the player chooses some position $i < n$ uniformly at random, replaces the element $a_i$ with $a_i -a_{i + 1}$, and then removes t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":16384},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10212K"},"statements":[{"statement_type":"Markdown","content":"Here is a game played with sequence $a_1, \\\\dots, a_n$. On each turn, the player chooses some position $i < n$ uniformly at random, replaces the element $a_i$ with $a_i -a_{i + 1}$, and then removes the element $a_{i + 1}$ from the sequence. This continues until there is only one element left. What is the expected value of the last element?\n\nThe first line of input contains a single integer $n$ ($2 <= n <= 4000$).\n\nThe second line of input contains $n$ integers $a_1, \\\\dots, a_n$ ($1 <= a_i <= 4000$).\n\nIf the answer is $frac(P, Q)$ such that $P$ and $Q$ are coprime, output a single integer which is $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$.\n\nPay attention to the non-standard memory limit.\n\n## Input\n\nThe first line of input contains a single integer $n$ ($2 <= n <= 4000$).The second line of input contains $n$ integers $a_1, \\\\dots, a_n$ ($1 <= a_i <= 4000$).\n\n## Output\n\nIf the answer is $frac(P, Q)$ such that $P$ and $Q$ are coprime, output a single integer which is $(P dot.op Q^(-1)) bmod (10^9 + 7)$. It is guaranteed that $Q not equiv 0 pmod 10^9 + 7$.\n\n[samples]\n\n## Note\n\nPay attention to the non-standard memory limit.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 4000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq 4000 $.  \n\n**Process**  \nAt each step, choose uniformly at random an index $ i \\in \\{1, 2, \\dots, n-1\\} $, and replace the sequence by:  \n$$\n(a_1, \\dots, a_{i-1}, a_i - a_{i+1}, a_{i+2}, \\dots, a_n)\n$$  \nThis reduces the sequence length by 1. Repeat until one element remains.\n\n**Objective**  \nCompute the expected value $ \\mathbb{E} $ of the final remaining element, and output $ P \\cdot Q^{-1} \\mod (10^9 + 7) $, where $ \\mathbb{E} = \\frac{P}{Q} $ in lowest terms.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10212K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}