405829: GYM102129 K Expected Value

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?

The first line of input contains a single integer $$$n$$$ ($$$2 \leq n \leq 4000$$$).

The second line of input contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 4000$$$).

If the answer is $$$\tfrac P Q$$$ such that $$$P$$$ and $$$Q$$$ are coprime, output a single integer which is $$$(P \cdot Q^{-1}) \bmod (10^9 + 7)$$$. It is guaranteed that $$$Q \not\equiv 0 \pmod{10^9+7}$$$.

2
2 1

1

Pay attention to the non-standard memory limit.