K. Expected Value
time limit per test
3 seconds
memory limit per test
16 mebibytes
input
standard input
output
standard output

Here is a game played with sequence $$$a_1, \dots, a_n$$$. On each turn, the player chooses some position $$$i \lt 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?

Input

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$$$).

Output

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}$$$.

Example
Input
2
2 1
Output
1
Note

Pay attention to the non-standard memory limit.