시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 64 | 47 | 30 | 68.182% |
The boboness of a sequence of integers $(x_1, x_2, \dots, x_n)$ is $\prod\limits_{i = 3}^n w(\max\{x_{i - 2}, x_{i - 1}, x_i\})$. Here, $1 \leq x_i \leq n$, and the values $w(1), w(2), \dots, w(n)$ are given.
Bobo would like to know the sum of boboness of all sequences satisfying $1 \leq x_i \leq n$. As this sum can be very large, he is interested only in the answer modulo $(10^9+7)$.
The input contains zero or more test cases, and is terminated by end-of-file. For each test case:
The first line contains an integer $n$ ($3 \leq n \leq 2000$).
The second line contains $n$ integers $w(1), w(2), \dots, w(n)$ ($1 \leq w(i) \leq 10^9$).
It is guaranteed that the sum of $n$ does not exceed $2000$.
For each test case, output an integer which denotes the sum taken modulo $(10^9+7)$.
3 1 2 3 4 1 1 1 1
72 256