18546번 - Expected Value 다국어

문제

Here is a game played with sequence a₁, . . . , 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 ≤ n ≤ 4000).

The second line of input contains n integers a₁, . . . , a_n (1 ≤ a_i ≤ 4000).

출력

If the answer is P/Q such that P and Q are coprime, output a single integer which is (P · Q⁻¹) mod (109 + 7). It is guaranteed that Q ≢ 0 (mod 10⁹ + 7).

제한

힌트

Pay attention to the non-standard memory limit.