시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 16 MB (추가 메모리 없음) | 72 | 31 | 29 | 46.774% |
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
1
Pay attention to the non-standard memory limit.