기댓값

시간 제한3초메모리 제한16 MB

요약

인접한 두 원소를 무작위로 골라 왼쪽 값을 두 값의 차로 바꾸고 오른쪽 원소를 지우는 과정을 하나가 남을 때까지 반복할 때, 마지막 원소의 기댓값을 10^9+7로 나눈 나머지로 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 확률, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

수열 $a_1, \dots, a_n$ 으로 게임을 한다. 매 턴마다 플레이어는 $i < n$ 인 위치 $i$ 를 균등한 확률로 하나 고르고, 원소 $a_i$ 를 $a_i - a_{i+1}$ 로 바꾼 뒤 수열에서 원소 $a_{i+1}$ 을 제거한다. 원소가 하나만 남을 때까지 이 과정을 반복한다. 마지막에 남는 원소의 기댓값은 얼마인가?

입력

첫째 줄에 정수 $n$ 이 주어진다. ( $2 \le n \le 4000$ )

둘째 줄에 $n$ 개의 정수 $a_1, \dots, a_n$ 이 주어진다. ( $1 \le a_i \le 4000$ )

출력

답을 $P/Q$ ( $P$ 와 $Q$ 는 서로소)라 할 때, $(P \cdot Q^{-1}) \bmod (10^9 + 7)$ 을 나타내는 정수 하나를 출력한다. $Q \not\equiv 0 \pmod{10^9 + 7}$ 임이 보장된다.

힌트

표준과 다른 메모리 제한에 주의하라.

예제1

예제 1
입력
```
2
2 1
```
예상 출력
```
1
```