|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||16 MB (추가 메모리 없음)||33||15||14||43.750%|
Here is a game played with sequence a1, . . . , an. On each turn, the player chooses some position i < n uniformly at random, replaces the element ai with ai − ai+1, and then removes the element ai+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 a1, . . . , an (1 ≤ ai ≤ 4000).
If the answer is P/Q such that P and Q are coprime, output a single integer which is (P · Q−1) mod (109 + 7). It is guaranteed that Q ≢ 0 (mod 109 + 7).
2 2 1
Pay attention to the non-standard memory limit.