시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 16 MB (추가 메모리 없음) 15 10 9 64.286%

문제

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

예제 입력 1

2
2 1

예제 출력 1

1

힌트

Pay attention to the non-standard memory limit.