Even Three is Odd

시간 제한2초메모리 제한512 MB

요약

1 이상 n 이하의 값을 갖는 모든 수열 x_1..x_n에 대해, 연속한 세 항의 최댓값에 대한 w 값을 모두 곱한 값의 합을 1e9+7로 나눈 나머지를 구한다.

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

문제

정수 수열 $(x_1, x_2, \dots, x_n)$ 의 boboness는 $\prod\limits_{i = 3}^n w(\max\{x_{i - 2}, x_{i - 1}, x_i\})$ 이다. 여기서 $1 \leq x_i \leq n$ 이고, 값 $w(1), w(2), \dots, w(n)$ 이 주어진다.

Bobo는 $1 \leq x_i \leq n$ 을 만족하는 모든 수열의 boboness 합을 알고 싶어 한다. 이 합은 매우 커질 수 있으므로 그는 $(10^9+7)$ 로 나눈 나머지에만 관심이 있다.

입력

입력은 0개 이상의 테스트 케이스로 이루어지며, 파일의 끝으로 종료된다. 각 테스트 케이스에 대해:

첫째 줄에 정수 $n$ 이 주어진다 ( $3 \leq n \leq 2000$ ).

둘째 줄에 $n$ 개의 정수 $w(1), w(2), \dots, w(n)$ 이 주어진다 ( $1 \leq w(i) \leq 10^9$ ).

$n$ 의 합이 $2000$ 을 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해, 합을 $(10^9+7)$ 로 나눈 나머지를 나타내는 정수를 출력한다.

예제1

예제 1
입력
```
3
1 2 3
4
1 1 1 1
```
예상 출력
```
72
256
```