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 \le n \le 4000$).

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

If the answer is $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}$.

Pay attention to the non-standard memory limit.