{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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$)."},{"iden":"output","content":"If 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$."},{"iden":"note","content":"Pay attention to the non-standard memory limit."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"You are given a sequence of n numbers. In each step, pick a random adjacent pair (i, i+1), replace a_i with a_i - a_{i+1}, and remove a_{i+1}. Repeat until one number remains. Find the expected value of that final number, modulo 10^9 + 7.","has_page_source":false}